- 描述
斐波那契数列大家应该很熟悉了吧。下面给大家引入一种新的斐波那契数列：M斐波那契数列。 M斐波那契数列F[n]是一种整数数列，它的定义如下：
F[0] = a
F[1] = b
F[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
Solution:
本题我们容易发现$F[0]=a,F[1]=b,F[2]=ab,F[3]=ab^2,F[4]=a^2b^3,F[5]=a^3b^5…$，设$f[i]表示第i个斐波拉契数$，则$F[n]=a^{f[n-1]}b^{f[n]},n≥2$
于是，$F[n]=a^{f[n-1]}b^{f[n]}\;mod\;p$，关键是$ a,b $指数会很大，由扩展欧拉定理（关于扩展欧拉定理）:
$a^n≡a^{n\;mod\;\phi (p)}\;mod\;p,\quad gcd(a,p)=1$，注意到$ p $为素数，于是$gcd(a,p)=1,\phi (p)=p-1$，
那么本题就直接套上矩阵快速幂取对$p-1$取模求出$a,b$的系数，然后再普通快速幂对$p$取模求$ans$就$OK$了。
代码：
/*题意是给定F[1]=a，F[2]=b，F[n]=F[n-1]*F[n-2]，求第n项对素数m取模*/#include#include#include#define il inline#define ll long long #define mem(p) memset(&p,0,sizeof(p))using namespace std;const ll mod = 1e9+7;ll a,b,n,phi=mod-1,mia,mib;struct mat{ll a[3][3],r,c;};il mat mul(mat x,mat y){ mat p; mem(p); p.r=x.r,p.c=y.c; for(int i=0;i<x.r;i++) for(int j=0;j<y.c;j++) for(int k=0;k<x.c;k++) p.a[i][j]=(p.a[i][j]+x.a[i][k]*y.a[k][j]%phi)%phi; return p;}il void fast(ll k){ mat p,ans; mem(p),mem(ans); p.r=p.c=2; p.a[0][0]=p.a[0][1]=p.a[1][0]=1; ans.r=1,ans.c=2; ans.a[0][0]=1,ans.a[0][1]=1; while(k){ if(k&1)ans=mul(ans,p); p=mul(p,p); k>>=1; } mib=ans.a[0][0];mia=ans.a[0][1];}il ll qpow(ll o,ll k){ ll ans=1; while(k) { if(k&1)ans=ans*o%mod; k>>=1; o=o*o%mod; } return ans;}int main(){ ios::sync_with_stdio(0); //cout<<phi<<endl;while(cin>>a>>b>>n){ if(n==0){cout<mod?a%mod:a)<<endl;continue;} if(n==1){cout<mod?b%mod:b)<<endl;continue;} if(n==2){cout<<a*b%mod<<endl;continue;} fast(n-2); // cout<<mia<<' '<<mib<<endl;cout<<qpow(a,mia)*qpow(b,mib)%mod<<endl; } return 0;}