M斐波那契数列
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 43 Accepted Submission(s) : 28
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem 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
Sample Output
0
60
Source
2013金山西山居创意游戏程序挑战赛——初赛（2）
题解：
题目中 f[n] =a ^? * b^? ，a，b的指数，刚好可以使用斐波那契数列求解，
矩阵快速幂求斐波那契数列
费马小定理：
若p是质数，且gcd（a，p）=1，则 a ^ (p-1) = 1 (mod p)
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mod=;
long long a,b;
int n;
long long pow(long long a,long long b)
{
long long res=;
while(b)
{
if (b&) res=(res*a)%mod;
a=(a*a)%mod;
b>>=;
}
return res;
}
long long mul(int n)
{
long long t[][]={,,,};//相当于pow中的a
long long ans[][]={,,,};//存最后的结果
long long tmp[][]; // 临时的
while(n)
{
if (n&)
{
for(int i=;i<;i++)
for(int j=;j<;j++)
tmp[i][j]=ans[i][j],ans[i][j]=;
for(int i=;i<;i++)
for(int j=;j<;j++)
for(int k=;k<;k++)
ans[i][j]=(ans[i][j]+tmp[i][k]*t[k][j])%(mod-);
}
for(int i=;i<;i++)
for(int j=;j<;j++)
{ tmp[i][j]=t[i][j]; t[i][j]=;}
for(int i=;i<;i++)
for(int j=;j<;j++)
for(int k=;k<;k++)
t[i][j]=(t[i][j]+tmp[i][k]*tmp[k][j])%(mod-);
n>>=;
}
return (pow(a,ans[][])*pow(b,ans[][]))%mod;
}
int main()
{
while(~scanf("%lld%lld%d",&a,&b,&n))
{
if (n==) printf("%lld\n",a%mod);
else if (n==) printf("%lld\n",b%mod);
else printf("%lld\n",mul(n));
} return ;
}