Day 19, 费波纳契数加总，求尾数输出值: 背后的数学规律

如题，我们这一次要试着设计出，能够计算出费波纳契数加总的尾数输出，我原本用了大数相加方式，但在输入值为8万多时，就爆掉了，所以我查询了网路，一直冒出来一个关键字:

Pisano period

我在这里简洁说明一下原理，费波纳契数是一个无止尽的数字，然而，若跟指定整数相除，留下来的余数会出现规律，称为Pisano period。

例如，将费波纳契数与3相除的余数，依序如下:
[0, 1, 1, 2, 0, 2, 2, 1]... ....然后就一直重複下去
若将费波纳契数相加后与3相除的余数，依序如下:
[0, 1, 2, 1, 1, 0, 2, 0]... ...然后就一直重複下去

以上我们发现一个共通点，按照 Pisano period，不管是费波纳契数还是费波纳契数加总，相应整数的余数週期是一致的，例如与3的余数週期，都是8循环一次。
然后，由于我们题目要求找出尾数，那么使用费波纳契数加总与10的余数週期就能找到解答，查询网路得知，10的余数週期是60，并且使用费波纳契数加总，程式输出前60的，10余数依序如下:
{0,1,2,4,7,2,0,3,4,8,
3,2,6,9,6,6,3,0,4,5
,0,6,7,4,2,7,0,8,9,8
,8,7,6,4,1,6,8,5,4,0
,5,6,2,9,2,2,5,8,4,3,
8,2,1,4,6,1,8,0,9,0}

那么，在参考许多程式后，我的程式如下:

#include<iostream>using namespace std;long long last_fibo_digit(long long n) {int period;int fibo_pisa[60]={0,1,2,4,7,2,0,3,4,8,3,2,6,9,6,6,3,0,4,5,0,6,7,4,2,7,0,8,9,8,8,7,6,4,1,6,8,5,4,0,5,6,2,9,2,2,5,8,4,3,8,2,1,4,6,1,8,0,9,0};period = n%60;    return fibo_pisa[period];}int main(){long long int n;cin>>n;cout<<last_fibo_digit(n)<<endl;return 0;}

结果: