鏈接：

時間限制：C/C++ 1秒，其他語言2秒 空間限制：C/C++ 262144K，其他語言524288K 64bit IO Format: %lld

題目描述

給你一個邊長為 n 的用硬幣擺成的實心三角形，請問把他倒過來最少需要多少步？ 例子：這是一個邊長為3的硬幣三角形

只要移動邊上的兩個硬幣，就可以把它到過來（注意是倒過來，不是旋轉(zhuǎn)角度），變成這樣：

聰明的 Prev1ous秒切了這道題，于是他希望來考考你 Prev1ous 經(jīng)過計算后發(fā)現(xiàn)，由于答案實在是太大了，所以他只關(guān)心答案對
23333333333333333取膜的結(jié)果，順帶一提這是個質(zhì)數(shù)。

輸入描述:

多組數(shù)據(jù)，第一行一個正整數(shù) T 表示有 T 組數(shù)據(jù) 接下來 T 行，每行一個正整數(shù) n 表示硬幣三角形的邊長

輸出描述:

一共 T 行，每行一個整數(shù)，表示移動的最小步數(shù)

示例1
輸入

3 1 3 5

輸出

0 2 5

說明
對于10%的數(shù)據(jù)：1≤n≤6,1≤T≤10
對于30%的數(shù)據(jù)：1≤n≤100,1≤T≤100
對于額外30%的數(shù)據(jù)：1≤n≤2×10^ 6 ,T=1
對于100%的數(shù)據(jù)：1≤n≤1018 ,1≤T≤1×105

題解：

正規(guī)做法不會，官方題解也沒看懂（哭o(╥﹏╥)o）
只能用其他小技巧：

我們看看
n從1開始為各值時，答案應(yīng)該是多少
n=1 2 3 4 5 6 7 8 9 10 11
0 1 2 3 5 7 9 12 15 18 22

然后。。
oeis查一下
第二次安利這個神奇的網(wǎng)站

發(fā)現(xiàn)給的樣例正好就是題目：三角形倒置問題
可以直接得到式子,利用公式做出

還有一個規(guī)律，從1開始，（1的行動次數(shù)為0）三角形邊長每增加1，行動次數(shù)增加1,1,1,2,2,2,3,3,3，4，4，4…從這一點出發(fā)，OEIS也不用了，也可以做出題目

總結(jié)

以上是生活随笔為你收集整理的像鱼的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。