UVA10229，輸出斐波那契數列第n項對2^m取模的值。我看到有用回圈數列計算的題解，之前也遇到過類似斐波那契數列求回圈節的題目。因為自己能力有限，所以想問一下在什么情況下，斐波那契數列存在回圈節呢
？求不吝賜教。
uj5u.com熱心網友回復：
這其實是個數學問題，答案是必然存在。對于斐波那契數列a[n]對m取模。
由于斐波那契數列的特征，只要存在a[j] mod m = a[k] mod m且a[j+1] mod m = a[k+1] mod m (j<k)，則a[j] ~ a[k-1]為回圈節。
考慮兩兩相鄰的斐波那契數 mod m的數對，最多只有m * (m - 1)種可能。
根據抽屜原理，a[0]~a[m * (m - 1) + 1]中必然存在相鄰數對存在重復。
因此必然存在回圈節。
uj5u.com熱心網友回復：
我明白了！！！謝謝大牛！！！uj5u.com熱心網友回復：
也就是說mod*(mod-1)一定是他的一個回圈節，雖然不一定是最短的。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6;
LL fib[N + 1];
void setfib(LL mod, LL cycle)
{
fib[0] = 1 % mod;
fib[1] = 1 % mod;
for(LL i=2; i<=cycle; i++)
fib[i] = (fib[i - 2] + fib[i - 1]) % mod;
}
int main()
{
LL n, m;
while(cin >> n >> m) {
LL mod = 1LL << m;
LL cycle = mod * 3 / 2;
setfib(mod, cycle);
cout << fib[--n % cycle] << endl;
}
return 0;
}
---------------------
作者：海島Blog
來源：CSDN
原文：https://blog.csdn.net/tigerisland45/article/details/79323943
著作權宣告：本文為博主原創文章，轉載請附上博文鏈接！
上邊的代碼是這道題的一個題解，我想問一下在這里為什么回圈節就直接是mod * 3 / 2了？如果方便的話可以解答一下嗎？
uj5u.com熱心網友回復：
<br />應該是n方種可能吧轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/91640.html
標籤：C++ 語言
上一篇：c語言 基于兩個鏈表實作存盤兩個班級的成績并降序排列 然后合并兩個鏈表 保持降序 但是合并失敗了，求大佬指點哪里出現了錯誤（merge為合并函式
下一篇：C語言求解，，感謝大佬