The i’th Fibonacci number f(i) is recursively de?ned in the following way: ? f(0) = 0 and f(1) = 1 ? f(i + 2) = f(i + 1) + f(i) for every 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 < 264 (a and b will not both be zero) and 1 ≤ 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
#include<iostream>
#include<fstream>
#include<string>
#include<map>//int dx[4]={0,0,-1,1};int dy[4]={-1,1,0,0};
#include<set>//int gcd(int a,int b){return b?gcd(b,a%b):a;}
#include<queue>
#include<cmath>
#include<stack>
#include<string.h>
#include<stdlib.h>
#include<cstdio>
#define mod 1e9+7
#define ll unsigned long long///这样才够大
#define maxn 1100
#define MAX 500005
#define ms memset
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000") ///在c++中是防止暴栈用的
ll a,b,n,t;
ll m,fib[maxn][maxn*6],cir[maxn];///m表示答案周期
ll Pow(ll x,ll y,ll m)
{ll t=1;x%=m;while(y>0){if(y&1) t=(t*x)%m;x=(x*x)%m;y>>=1;}return t;
}
/*
题目大意：给定a,b,n;
求a^b个斐波那契数，且对n取余。因为涉及到取余，n的范围只是一千，
根据紫书上的分析和自己打表找规律，
可知，其周期范围最多是n*n,
当然，可以实现打表自己看最大的值，
不可能真的有1e6的数量级的，
不然数组开不下了。
这样题目思路就清晰了许多，
对于每个n,预处理其周期并记录即可。
再加上个快速幂（PS:这题我到现在还没过，，
玄学，，不知道为什么，debug的数据都跑过了）
*/void init()
{cir[1]=1;memset(fib[1],0,sizeof(fib[1]));fib[1][1]=1; ll j;for(int i=2;i<=1000;i++){fib[i][0]=0,fib[i][1]=1;for(j=2;;j++){fib[i][j]=(fib[i][j-1]+fib[i][j-2])%i;if(fib[i][j]==1&&fib[i][j-1]==0){cir[i]=j-1;break;}}for(;j<maxn*6;j++) fib[i][j]=(fib[i][j-1]+fib[i][j-2])%i;}
}int main()
{init();scanf("%lld",&t);while(t--){scanf("%lld%lld%lld",&a,&b,&n);int index=Pow(a,b,cir[n]);printf("%lld\n",fib[n][index]);}return 0;
}