本文主要是介绍Colossal Fibonacci Numbers! UVA - 11582，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Colossal Fibonacci Numbers!
UVA - 11582 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
• 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
题意：给定三个数a,b,n.函数f(n)是斐波那契函数，求f(a^b)%n。
题解：红书上的一道题，难点在于a,b的值过大，但是通过设F(i) =f（i）mod n， 很容易发现，F（x）具有周期性，当F(i),F(i-1)重复时，根据递推公式可知周期为i-1；利用快速幂公式找到F(a^b)即可。（a,b范围过大 需要用unsigned long long输入）。
AC代码：
#include<iostream>
#include<cstdio>
using namespace std;
unsigned long long a,b;
int n,t;
const int maxn = 1005;
int f[maxn*maxn];
int fun(unsigned long long a,unsigned long long b,int c)
{if(b==0)return 1;int s = fun(a,b/2,c);s = s*s%c;if(b&1)s=s*a%c;return s;
}
int get(int x)
{f[0]=0;f[1]=1;int i=2;while(1){f[i]=(f[i-1]+f[i-2])%x;if(f[i]==1&&f[i-1]==0)break;i++;}return i-1;
}
int main()
{scanf("%d",&t);for(int i=1;i<=t;i++){scanf("%llu%llu%d",&a,&b,&n);if(a==0||n==1)cout<<0<<endl;else{int ff = get(n);int ans = fun(a%ff,b,ff);printf("%d\n",f[ans]);}}return 0;
}
这篇关于Colossal Fibonacci Numbers! UVA - 11582的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
