Description
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
Hint
题意
题解：
第一道矩阵快速幂模板练习
AC代码
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long LL;
int A,B,n;
struct mat {
int rix[2][2];
};
mat mul(mat x,mat y){
mat c;
for (int i = 0;i < 2; ++i) for (int j = 0; j < 2 ;++j) c.rix[i][j] = 0;
for (int i = 0;i < 2 ; ++i){
for (int j = 0;j < 2; ++j){
for (int k = 0;k < 2; ++k){
c.rix[i][j] += x.rix[i][k]*y.rix[k][j];
c.rix[i][j] %= 7;
}
}
}
return c;
}
mat q_mod(mat a,int b){
mat tm;
tm.rix[1][0] = tm.rix[0][1] = 0;
for (int i = 0;i < 2; ++i) tm.rix[i][i] = 1;
while (b){
if (b&1) tm = mul(tm,a);
a = mul(a,a);
b>>=1;
}
return tm;
}
int main(){
while (scanf("%d%d%d",&A,&B,&n),A&&B&&n){
int ans[2][1];
for (int i = 0;i < 2; ++i) ans[i][0] = 0;
int temp[2][1]; temp[0][0] = temp[1][0] = 1;
mat q;
q.rix[0][0] = A; q.rix[0][1] = B; q.rix[1][0] = 1; q.rix[1][1] = 0;
mat ed = q_mod(q,n-1);
for (int i = 0;i < 2; ++i){
for (int j = 0;j < 1; ++j){
for (int k = 0;k < 2; ++k){
ans[i][j] += ed.rix[i][k]*temp[k][j];
ans[i][j] %= 7;
}
}
}
printf("%d\n",ans[1][0]); //算出来的好像是f(n+1) 所以取下面的f(n)
}
return 0;
}