Problem F: Colossal Fibonacci Numbers!

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)  for every i ≥ 0

Your task is to compute some values of this sequence. Input begins with an integer t ≤ 10,000, the number of test cases. Each test case consists of three integers a,b,nwhere 0 ≤ a,b < 264 (a and b will not both be zero) and 1 ≤ n ≤ 1000. 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

一.大数取模，幂取模，模的计算方法

1. (a+b)%n=(a%n+b%n)%n 2.(a-b)%n=(a%n-b%n+n)%n 3.(a*b)%n=(a%n*b%n)%n

一.问题分析及解决
想啊，这个问题明明以前都做过很类似的问题的，F[i]%n，那么应该很自然的去想F[i]%n=(F[i-1]%n+F[i-2]%n)%n,接下来应该就会发现要求的东西只要知道前两个数的模就好了，那就很自然的转化到以前的找规律问题上来 #include #include #include using namespace std; typedef unsigned long long ull; const int maxn=1000+10; ull F[maxn*maxn]; int power(ull a, ull b, int t) { ull result = 1; while(b) { if(b%2) { result = (a*result)%t; } a = (a*a)%t; b/=2; } return result; } int main() { freopen("/Users/zhangjiatao/Documents/暑期训练/input.txt","r",stdin); int T; cin>>T; while(T--) { ull a,b,n,l; int flag=1; cin>>a>>b>>n; F[0]=0; F[1]=1; for(ull i=2;i<=n*n;i++) { F[i]=(F[i-1]%n+F[i-2]%n)%n; if(F[i]==F[1]&&F[i-1]==F[0]) { l=i-1; break; } } if(a == 0 || n == 1) printf("0 "); else cout<