题意：

看白书

要点：

先斐波那契数列打个表，然后用同余与模算术，找个规律就行。注意数的最大值为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;}