題意：

給出64位整數a、b以及不超過1000的正整數n，求斐波那契數列第a ^ b項模n的結果。 輸入：情況數T，之后T行每行a、b、n。 輸出：斐波那契數列第a ^ b項模n的結果。

分析：由于斐波那契數列的每一項都是由前兩項相加得來，并且每一項都對n取模，所有 每一項的情況一共有n種，而相鄰兩項若組成有序數對，則不同的數對的情況也只有 n ^ 2種，所以只需要計算n * n項就可以找到數列規律。

題目：

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

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.

Output

For each test case, output a single line containing the remainder of f(a b ) upon division by n.

Sample Input

3

1 1 2

2 3 1000

18446744073709551615 18446744073709551615 1000

Sample Output

1

21

250

AC代碼

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; typedef unsigned long long ull; int t; ull m,n; ull dp[1000010];/*范圍*/ int k; int dfs(ull a,ull b,int c) {int ans=1;int q=a%c;while(b){if(b&1)ans=ans*q%c;q=q*q%c;b>>=1;/*care 別忘了加=，>>是一個數學運算符號*/}return ans; } int main() {scanf("%d",&t);while(t--){scanf("%llu%llu%d",&m,&n,&k);if(m==0||k==1){printf("0\n");continue;}dp[0]=0;dp[1]=1;int c;for(int i=2; i<=k*k; i++){dp[i]=(dp[i-1]+dp[i-2])%k;if(dp[i]==1&&dp[i-1]==0)/*已經找出一個周期長度了，在k*k內一定找得到*/{c=i-1;break;}}int ans=dfs(m,n,c);printf("%llu\n",dp[ans]);}return 0; }

?

總結

以上是生活随笔為你收集整理的Colossal Fibonacci Numbers! UVA - 11582（斐波那契求模）+快速幂+周期规律的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。