UVA

找Fn =( Fn-1 + Fn-2 ) mod n 的循环节
暴力找即可
 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 typedef unsigned long long ll;
 5 using namespace std;
 6 const int MAXN = 1023;
 7 ll f[MAXN][MAXN*10];
 8 int circle[MAXN];
 9 
10 void init(){
11     for(int k = 2; k<= 1000; k++){
12         f[k][0] = 0, f[k][1] = 1;
13         for(int i = 2; ; i++){
14             f[k][i] = (f[k][i-1] + f[k][i-2])%k;
15             if(f[k][i] == 1 && f[k][i-1] == 0){
16                 circle[k] = i-1;
17                 break;
18             }
19         }
20     }
21 }
22 ll quick_mod(ll a, ll b, ll mod){
23     ll ans = 1;
24     while(b > 0){
25         if(b&1){
26             b--;
27             ans = ans*a%mod;
28         }
29         b >>= 1;
30         a = a*a%mod;
31     }
32     return ans;
33 }
34 void slove(ll a, ll b, int n){
35     int res = quick_mod(a%circle[n], b, circle[n]);
36     cout << f[n][res] << endl;
37 }
38 int main() {
39     //freopen("data.in.txt", "r", stdin);
40    // freopen("data.out.txt", "w", stdout);
41     int t, n;
42     ll a, b;
43     init();
44     scanf("%d", &t);
45     while(t--) {
46         cin >> a >> b >> n;
47         if(n == 1 || a == 0) cout<<0 << endl;;
48         else slove(a, b, n);
49     }
50     return 0;
51 }