（1）这道题要用到 unsigned long long， 弄了我好久
这道题范围可以达到2的64次方-1， 而long long 最多到2的63次方-1，
而unsigned long long可以到2的64次方-1，所以要用这个类型，注意这个类型只有正数
输入输出用printf貌似要用%llu， 我直接用cin cout方便一些
（2）这道题因为是去模的， 所以我们可以找规律， 可以发现斐波那契数列这样
一直取模是肯定会重复的，所以我们可以找到一个周期。所以我们就判断a的b次方
在这个周期中的哪一个位置， 就可以得出答案了
#include<iostream>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;typedef unsigned long long ull;
const int MAXN = 1123;
int f[MAXN][MAXN*6], period[MAXN], T;int cal(ull a, ull b, int p)
{int ret = 1;while(b){if(b & 1) ret = ret * a % p;b >>= 1;a = a * a % p;}return ret;
}int solve(ull a, ull b, int p)
{if(a == 0 || p == 1) return 0; //注意特殊情况 int t = cal(a % period[p], b, period[p]); //注意这里要取模 return f[p][t];
}void init() //预处理
{REP(p, 2, 1001){f[p][0] = 0; f[p][1] = 1;for(int i = 2; ; i++){f[p][i] = (f[p][i-1] + f[p][i-2]) % p;if(f[p][i-1] == 0 && f[p][i] == 1) // 看是否重复 {period[p] = i - 1;break;}}}
}int main()
{init();cin >> T;while(T--){ull a, b; int p;cin >> a >> b >> p;cout << solve(a, b, p) << endl;}return 0;
}