zufe 问题 : Matrix Fast Power

Matrix Fast Power"/>

zufe 问题 : Matrix Fast Power

这道题就是找循环节

#include<bits/stdc++.h>using namespace std;int a[10000][2],book[10000];int ff(int t)
{int num = 0 ;while(t){num += t % 10;t /= 10;}return num;
}int main()
{int T;cin >> T;for(int u = 1; u <= T ; u ++){int l, r;long long n ;cin >> l >> r >> n;a[1][0] = l;a[1][1] = l;a[2][0] = r;a[2][1] = l + r;for(int i = 3; i < 100 ; i ++){a[i][0] = ff(a[i-1][0]) + ff(a[i-2][0]);a[i][1] = a[i-1][0] + a[i][0];}//for(int i = 1; i <= 10 ; i ++)//  cout << a[i][0] << " ";//cout << endl;if(n < 100){cout << "Case #" << u << ": " << a[n][0] << endl;continue;}int s1,s2;for(int i = 1; i < 100 ; i ++){for(int j = i + 1; j < 100 ; j ++)if(a[i][0] == a[j][0] && a[i][1] == a[j][1]){s1 = i - 1; s2 = i;}}int num = 0,t;for(int i = 1; i < 100 ; i ++){if(a[i][0] == a[s1][0] && a[i+1][0] == a[s2][0]){t = i;break;}num ++;}n -= num;//cout << n << endl;num = 2;for(int i = t + 2 ; i < 100;i ++){if(a[i][0] == a[s1][0] && a[i+1][0] == a[s2][0])break;num ++;}//cout << num << endl;n %= num;if(n == 0 )cout << "Case #" << u << ": " << a[s1 + num-1][0] << endl;elsecout << "Case #" << u << ": " << a[s1 + n - 1][0] << endl;}return 0;
}