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 ）
Output
对每组测试数据请输出一个整数F[n]，由于F[n]可能很大，你只需输出F[n]对1000000007取模后的值即可，每组数据输出一行。
Sample Input
0 1 0 6 10 2
Sample Output
0 60
解题思路：这道题题意很好懂，就是有多组测试数据，每组数据包括a,b,n（ 0 <= a, b, n <= 10^9 ）(所以均需要用long long型)然后可以利用矩阵快速幂求出对应n值的a的幂value2和b的幂value1,由于value2和value1都非常大，可能超过long long 型，且又分别作为a的幂和b的幂，由费马小定理(a^b%mod=a^(b%(mod-1))%mod)分别给a和b降幂，最后即可计算出结果；
代码如下：
#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <cstring> using namespace std; typedef long long ll; const ll mod=1e9+7; //构造结构体 struct matrix{ ll m[2][2]; matrix(){ memset(m,0,sizeof(m)); } }; //矩阵相乘 matrix mat_multi(matrix a,matrix b){ matrix c; for(int i=0;i<2;i++){ for(int j=0;j<2;j++){ c.m[i][j]=0; for(int k=0;k<2;k++){ c.m[i][j]+=(a.m[i][k]*b.m[k][j])%(mod-1); c.m[i][j]%=(mod-1); } } } return c; } //矩阵快速幂 matrix mat_quickpow(matrix d,ll e){ matrix ans; for(int i=0;i<2;i++){ for(int j=0;j<2;j++){ if(i==j) ans.m[i][j]=1; else ans.m[i][j]=0; } } while(e){ if(e&1) ans=mat_multi(ans,d); d=mat_multi(d,d); e/=2; } return ans; } //快速幂 ll quickpow(ll a,ll b){ ll sum2=1; while(b){ if(b&1) sum2=(sum2*a)%mod; a=(a*a)%mod; b/=2; } return sum2; } //主函数 int main(){ ll a,b,n; while(scanf("%lld %lld %lld",&a,&b,&n)!=EOF){ matrix ans,d; ll value1,value2; ll sum2=0; ll sum=0; d.m[0][0]=d.m[0][1]=d.m[1][0]=1; d.m[1][1]=0; ans=mat_quickpow(d,n); value1=ans.m[0][1]; value2=ans.m[1][1]; sum2=(quickpow(a,value2)*quickpow(b,value1))%mod; printf("%lld ",sum2); } return 0; }