题意：
看白书
要点：
先斐波那契数列打个表，然后用同余与模算术，找个规律就行。注意数的最大值为2^64，用long long型还不够，必须要用unsigned long long型。
#include#include #include #include int fibo[1025][8000];int g[1025];int pow_mod(unsigned long long a,unsigned long long n, int m)//注意2^64要用unsigned long long型{ if (n == 0) return 1; int x = pow_mod(a, n / 2, m); unsigned long long ans =(unsigned long long)x*x%m; if (n % 2 == 1) ans = ans*a%m; return (int)ans;}int main(){ unsigned long long a, b; int n,t,i,x; for (n = 2; n <= 1000; n++) { fibo[n][0] = 0; fibo[n][1] = 1; for (i = 2;; i++) { fibo[n][i] = (fibo[n][i - 1] % n + fibo[n][i - 2] % n) % n; if (fibo[n][i] == 1 && fibo[n][i - 1] == 0) //出现一样的说明重复了 { g[n] = i-1; break; } } } scanf("%d", &t); while (t--) { scanf("%llu%llu%d", &a, &b, &n); if (a == 0 || n == 1) //n=1时前面没打表,g[1]=0会RE printf("0\n"); else { x = pow_mod(a%g[n], b, g[n]); printf("%d\n", fibo[n][x]); } } return 0;}