A number sequence is defined as follows:
f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
Given A, B, and n, you are to calculate the value of f(n).
Input
The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.
Output
For each test case, print the value of f(n) on a single line.
Sample Input
1 1 3
1 2 10
0 0 0
Sample Output
2
5
题意：
求斐波那契数列的第n项。
题解：
由于n很大，所以一般的递推肯定是不行的。可以借助矩阵高效地求解，把斐波那契数列的递推式表示成矩阵可以得到下面的式子。
记这个矩阵为A，则有
因此只要求出A^{n-2}就可以求出Fn了。A的幂可以通过快速幂运算很快求得。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int mod=7;
struct Matrix
{
int a[2][2];
Matrix()
{
memset(a,0,sizeof(a));
}
void init()
{
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
a[i][j]=i==j?1:0;
}
Matrix operator *(const Matrix &B)
{
Matrix C;
for(int i=0;i<2;i++)
for(int k=0;k<2;k++)
for(int j=0;j<2;j++)
C.a[i][j]=(C.a[i][j]+a[i][k]*B.a[k][j])%mod;
return C;
}
Matrix operator ^(int n)
{
Matrix res,A=(*this);
res.init();
while(n)
{
if(n&1)
res=res*A;
A=A*A;
n>>=1;
}
return res;
}
};
int main()
{
int a,b,n;
while(cin>>a>>b>>n,a||b||n)
{
Matrix A;
a%=mod,b%=mod;
if(n<3)
{
cout<<"1"<<endl;
continue;
}
A.a[0][0]=a;
A.a[0][1]=b;
A.a[1][0]=1;
A=A^(n-2);
cout<<(A.a[0][0]+A.a[0][1])%mod<<endl;
}
return 0;
}