斐波那契数的皮萨诺周期

• fibonacci数为f0=0, f1=1, fi = f(i-1)+f(i-2)
• pisano period指的是一个序列对n取模后的周期
• fibonacci的周期性明显可见
  • 对2取模结果为：0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0
  • fibonacci对3取模结果为：0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1
• 此性质在用于计算超大fibonacci数时非常有用，以下为数个例子

fibonacci序列之和的最低位

• 首先计算出模10的pisano period，再根据周期性求解int pisano(long long n, long long m, vector& v){ long long a = 0; long long b = 1; v.push_back(0); v.push_back(1); for (int i = 2; i <= n; ++i) { long long t = b; b = a + b; a = t; b %= m; v.push_back(b); if(i & 1 == 1){ int r = (i >> 1) + 1; int j = 0, k = r; /* for(auto e:v) cout << e << ' '; cout << endl; */ for(; k <= i; j++, k++){ if(v[j] != v[k]) break; } //cout << k << ' ' << i << endl; if(k == i+1) return r; } } return 0; } long long fibonacci_sum_best(long long n) { if (n <= 1) return n; vectorv; int p = pisano(n, 10, v); // for(auto e:v) // cout << e << ' '; // cout << endl; // cout << "get pisano " << n << " " << p << endl; if(p == 0) return accumulate(v.begin(), v.end(), 0) % 10; else{ int period_sum = accumulate(v.begin(), v.end(), 0) % 10; int c = n / p; int sum = accumulate(v.begin(), v.begin() + (n % p) + 1, 0) + period_sum * c; return sum % 10; } }