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
题解:把系数矩阵的数换下即可
代码:
#include<stdio.h>
#include<string.h>
#define MAX 10
typedef long long ll;
ll p,q,MOD=7;
struct mat{
ll a[MAX][MAX];
};
mat operator *(mat x,mat y) //重载*运算
{
mat ans;
memset(ans.a,0,sizeof(ans.a));
for(int i=1;i<=2;i++){
for(int j=1;j<=2;j++){
for(int k=1;k<=2;k++){
ans.a[i][j]+=x.a[i][k]*y.a[k][j];
ans.a[i][j]%=MOD;
}
}
}
return ans;
}
mat qsortMod(mat a,ll n) //矩阵快速幂
{
mat t;
t.a[1][1]=p;t.a[1][2]=q; //变式的系数
t.a[2][1]=1;t.a[2][2]=0;
while(n){
if(n&1) a=t*a; //矩阵乘法不满足交换律,t在前
n>>=1;
t=t*t;
}
return a;
}
int main()
{
ll n;
while(scanf("%lld%lld%lld",&p,&q,&n)!=EOF)
{
if(p==0&&q==0&&n==0)
break;
if(n==1) printf("1
");
else if(n==2) printf("1
");
else{
mat a;
a.a[1][1]=1;a.a[1][2]=0;
a.a[2][1]=1;a.a[2][2]=0;
a=qsortMod(a,n-2);
printf("%lld
",a.a[1][1]);
}
}
return 0;
}