| Time Limit: 1000MS | Memory Limit: 32768KB | 64bit IO Format: %I64d & %I64u |
Description
M斐波那契数列F[n]是一种整数数列，它的定义如下：
F[0] = a
F[1] = b
F[n] = F[n-1] * F[n-2] ( n > 1 )
现在给出a, b, n，你能求出F[n]的值吗？
Input
输入包含多组测试数据；
每组数据占一行，包含3个整数a, b, n（ 0 <= a, b, n <= 10^9 ）
每组数据占一行，包含3个整数a, b, n（ 0 <= a, b, n <= 10^9 ）
Output
对每组测试数据请输出一个整数F[n]，由于F[n]可能很大，你只需输出F[n]对1000000007取模后的值即可，每组数据输出一行。
Sample Input
0 1 0
6 10 2
6 10 2
Sample Output
0
60
60
Source
2013金山西山居创意游戏程序挑战赛——初赛（2）
题意如题。
题解：解题过程中会发现a和b的指数是斐波那契数列，b的指数是f[n]，a的指数是f[n-1]。
构造{Fn+1,Fn,Fn,Fn-1}的矩阵，当n=1的时候是{1,1,1,0}，单位矩阵为{1,0,0,1}。
利用矩阵快速幂可以求出a和b的指数，在这个过程中还要用到费马小定理。
费马小定理:x的y次幂对M取模，如果M为素数且x和M互素，可以将y对(M-1)取模后再将结果对M取模。
即如果p是质数，且gcd(a,p)=1，那么 a(p-1)≡1（mod p）。
然后求a的an次幂和b的bn次幂的乘积并取余，分别利用二分快速幂即可。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define mod 1000000006
#define mod2 1000000007
typedef long long ll;
struct matrix
{
ll data[][];
};
matrix I= {,,,};
matrix multi(matrix a,matrix b)
{
matrix c;
memset(c.data,,sizeof(c.data));
for(int i=; i<; i++)
for(int j=; j<; j++)
for(int k=; k<; k++)
{
c.data[i][j]+=(a.data[i][k]%mod)*(b.data[k][j]%mod);
c.data[i][j]%=mod;
}
return c;
}
matrix pow(matrix a,ll b)
{
matrix ans=I;
while(b)
{
if(b&)
{
ans=multi(ans,a);
b--;
}
b>>=;
a=multi(a,a);
}
return ans;
}
ll pow2(ll a,ll b)
{
ll ans=;
while(b)
{
if(b&)
{
ans*=a;
ans%=mod2;
b--;
}
b>>=;
a*=a;
a%=mod2;
}
return ans;
}
int main()
{
ll aa,bb,an,bn,n;
while(scanf("%lld%lld%lld",&aa,&bb,&n)!=EOF)
{
matrix a= {,,,};
matrix ans;
ans=pow(a,n);
bn=ans.data[][];
an=ans.data[][];
//cout<<"a: "<<an<<" b: "<<bn<<endl;
ll ans2=((pow2(aa,an)%mod2)*(pow2(bb,bn)%mod2))%mod2;
printf("%lld\n",ans2);
}
return ;
}