# 斐波那契数的皮萨诺周期

• 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<long long>& 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;

vector<long long>v;
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;
}
}
``````