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, n where 0 ≤ a, b < 2 64 (a and b will not both be zero) and 1 ≤ n ≤ 1000.
For each test case, output a single line containing the remainder of ƒ(ab ) upon division by n.
3
1 1 2
2 3 1000
18446744073709551615 18446744073709551615 1000
1
21
250
题目大意：
给出a,b,n,让你计算f(a^b)%n,f(n)=f(n-1)+f(n-2);
因为是%n所以余数最多n*n种，于是我们就可以用快速幂求出是在数列中是第几个数，然后代入f[]
输出就可以了~
操作代码如下：（注：n&1为真则n为奇数）
#include<iostream> #include<cstdio> using namespace std; #define ll unsigned long long const int maxx=1100; int f[maxx*maxx]; int pow(ll m,ll n,int k) { int b=1; while(n>0) { if(n&1) { b=(b*m)%k; } n=n>>1; m=(m*m)%k; } return b; } int main() { int t; scanf("%d",&t); while(t--) { ll a,b; int n,m; scanf("%llu%llu%d",&a,&b,&n); if(n==1||a==0) printf("0\n"); else { f[0]=0; f[1]=1; m=n*n+10; int s; for(int i=2; i<=m; i++) { f[i]=(f[i-1]+f[i-2])%n; if(f[i]==f[1]&&f[i-1]==f[0]) { s=i-1; break; } } int k=pow(a%s,b,s); printf("%d\n",f[k]); } } return 0; }
Colossal Fibonacci Numbers! UVA - 11582（快速幂，求解）
原文：https://www.cnblogs.com/dwj-2019/p/11366131.html