M斐波那契数列
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 560 Accepted Submission(s): 156
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
//尽管知道矩阵的快速幂和一般数的快速幂，但数论太差，以为a^k%mod=a^(k%mod)%mod,其实这是大错特错，好像可以根据欧拉函数推出a^k%mod=a^(k%（mod-1）)%mod
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
const int mod=1000000007;
//N表示矩阵的N次幂
int aa,bb,N;
//此处假设矩阵为3*3阶
//origin存放需计算的矩阵，res存放答案矩阵
struct matrix
{
__int64 a[3][3];
}origin,res;
//直接将2个矩阵相乘x*y,返回计算后的矩阵
matrix multiply(matrix x,matrix y)
{
matrix temp;
memset(temp.a,0,sizeof(temp.a));
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
for(int k=0;k<2;k++)
{
temp.a[i][j]+=x.a[i][k]*y.a[k][j];
temp.a[i][j]=temp.a[i][j]%(mod-1);
}
}
}
return temp;
}
//将res初始化为单位矩阵，人为输入origin
void init()
{
origin.a[0][0]=origin.a[0][1]=origin.a[1][0]=1;
origin.a[1][1]=0;
//将res.a初始化为单位矩阵
memset(res.a,0,sizeof(res.a));
res.a[0][0]=res.a[1][1]=1;
}
//矩阵快速幂的计算
void calc(int n)
{
while(n)
{
if(n&1)
res=multiply(res,origin);
n>>=1;
origin=multiply(origin,origin);
}
}
__int64 optimized_pow_n(__int64 x, __int64 n)
{
__int64 pw = 1;
while (n > 0)
{
if (n & 1)
pw *= x;
pw=pw%mod;
x *= x;
x=x%mod;
n >>= 1;
}
return pw;
}
int main()
{
while(cin>>aa>>bb>>N)
{
init();
calc(N);
// printf("%I64d %I64d\n",res.a[0][1],res.a[1][1]);
__int64 temp1=optimized_pow_n((__int64)aa,(__int64)res.a[1][1]);
__int64 temp2=optimized_pow_n((__int64)bb,(__int64)res.a[0][1]);
__int64 temp=(temp1%mod)*(temp2%mod)%mod;
printf("%I64d\n",temp);
}
return 0;
}