The i'th Fibonacci number f(i) is recursively defined in the following way:     • f(0) = 0 and f(1) = 1     • f(i + 2) = f(i + 1) + f(i) forevery i ≥ 0   Your task is to compute some values of this sequence. Input Input begins with an integer t ≤ 10, 000, the number of test cases. Each test case consists of three integers a, b, n where 0 ≤ a, b < 2^64 (a and b will not both be zero) and1 ≤ n ≤ 1000. Output For each test case, output a single line containing the remainder of f(ab) upon division by n. Sample Input 3 1 1 2 2 3 1000 18446744073709551615 18446744073709551615 1000 Sample Output 1 21 250     问题链接：UVA11582 Colossal Fibonacci Numbers! 问题简述：（略） 问题分析：   Fibonacci数列各项进行模除后，必然从某项开始出现循环。利用这个循环，数列就不用无限计算下去了。 程序说明：（略） 题记：（略） 参考链接：（略）   AC的C++语言程序如下： /* UVA11582 Colossal Fibonacci Numbers! */ #include //#define DEBUG using namespace std; typedef unsigned long long ULL; const int N = 1000; int fib[N * N]; // 快速模幂 ULL powmod(ULL x, ULL n, ULL m) { ULL result = 1; for(; n; n>>=1) { if(n & 1) { result *= x; result %= m; } x *= x; x %= m; } return result; } int main() { int t; scanf("%d", &t); while(t--) { ULL a, b; int n, M = 2; scanf("%llu%llu%d", &a, &b, &n); // 计算数列到出现循环为止（模除n） fib[0] = 0; fib[1] = 1 % n; for(int i=2; i<=n * n; i++) { fib[i] = (fib[i - 2] + fib[i - 1]) % n; if(fib[i - 2] == 1 && fib[i - 1] == 0) { M = i - 1; #ifdef DEBUG printf("M=%d ", M); #endif break; } } int k = powmod(a % M, b, M); printf("%d ", fib[k]); } return 0; }