又见斐波那契数列
时间限制： 1000 ms | 内存限制：65535 KB
难度： 4
- 描述
-
斐波那契数列大家应该很熟悉了吧。下面给大家引入一种新的斐波那契数列：M斐波那契数列。 M斐波那契数列F[n]是一种整数数列，它的定义如下：
F[0] = aF[1] = bF[n] = F[n-1] * F[n-2] ( n > 1 )现在给出a, b, n，聪明的你能求出F[n]的值吗？
- 输入
- 输入包含多组测试数据； 每组数据占一行，包含3个整数a, b, n（ 0 <= a, b, n <= 10^9 ） 输出
- 对每组测试数据请输出一个整数F[n]，由于F[n]可能很大，你只需输出F[n]对1000000007取模后的值即可，每组数据输出一行。 样例输入
-
0 1 0 6 10 2
样例输出 -
0 60
上传者 - 解题思路：这个题需要用到费马小定理，要先知道什么叫做费马小定理。
- 实际上就是这么一个式子 a^(p-1)≡1 (mod p)， 意思是在取模的情况下这两边是相等的（p是质数时）。
- 当p为质数时可以这么用，(a^b) %p=a^(b%(p-1))。
- 但为什么这么用呢？
-
- b是一个质数的时候，可以分解成k(p-1)+c （c是b%（p-1）的余数）。
- 。。。
- 另外本题先通过找规律得到这个：
-
f(0)=a (1,0)
f(1)=b; (0,1)
f(2)=ab (1,1)
f(3)=abb (1,2)
f(4)=abbab (2,3)
f(5)=abbababb (3,5)
f(6)=abbababbabbab (5,8)
所以F(n)= [a^f(n-1) * b^f(n)] %mod = a^[f(n-1)%mod-1] * b^[f(n)%mod-1] %mod;
f(n)是一个标准的斐波那契数列，用矩阵快速幂求出来之后然后分别通过快速幂求a的幂，b的幂，然后可得出结果。
#include#include #include #define MOD 1000000006#define MOD2 1000000007using namespace std;struct matrix{ long long int m[2][2];};matrix base,ans;void init(){ //只初始化base和ans(单位矩阵) memset(base.m,0,sizeof(base.m)); memset(ans.m,0,sizeof(ans.m)); for(int i=0;i<2;i++){ ans.m[i][i]=1; } base.m[0][0]=base.m[0][1]=base.m[1][0]=1;}matrix multi(matrix a,matrix b){ matrix t; for(int i=0;i<2;i++){ for(int j=0;j<2;j++){ t.m[i][j]=0; for(int k=0;k<2;k++){ t.m[i][j]=(t.m[i][j]+(a.m[i][k]%MOD)*(b.m[k][j]))%MOD; } } } return t;}long int fast_matrix(int n){ while(n){ if(n&1){ ans=multi(ans,base); } base=multi(base,base); n>>=1; } return ans.m[1][0];}long long int fast_power(long long int a,long long int n){ long long int ans=1,p=a; while(n){ if(n&1){ ans=((ans%MOD2)*(p%MOD2))%MOD2; } n>>=1; p=((p%MOD2)*(p%MOD2))%MOD2; } return ans;}int main(){ long long int a,b,n; while(~scanf("%lld %lld %lld",&a,&b,&n)){ if(n==0){ printf("%lld\n",a%MOD2); continue; } if(n==1){ printf("%lld\n",b%MOD2); continue; } if(n==2){ printf("%lld\n",a*b%MOD2); continue; } init(); long long int f=fast_matrix(n);//fib(n) long long int f2=ans.m[1][1];//fib(n-1) long long int m1=fast_power(a,f2); long long int m2=fast_power(b,f); long long int ans=m1*m2%MOD2; printf("%lld\n",ans); } return 0;}