Problem 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
Author
CHEN, Shunbao
Source
快速幂板子题
#include <stdio.h>
#define mod 7
#define ll long long
typedef struct matrix {
ll mat[2][2];
}matrix;
matrix unit_matrix = {1, 0, 0, 1}; //单位矩阵
matrix mul(matrix a, matrix b) {
matrix res;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++) {
res.mat[i][j] = 0;
for (int k = 0; k < 2; k++) {
res.mat[i][j] = res.mat[i][j] + a.mat[i][k] * b.mat[k][j];
res.mat[i][j] = res.mat[i][j] % mod;
}
}
return res;
}
matrix pow_matrix(matrix a, ll n) {
matrix res = unit_matrix;
while (n != 0) {
if (n & 1)
res = mul(res, a);
a = mul(a, a);
n >>= 1;
}
return res;
}
int main() {
ll n,a,b;
while (scanf("%lld %lld %lld",&a,&b,&n)!=EOF)
{
if(a==0&&b==0&&n==0) break;
if (n <= 2)
{
printf("1\n");
continue;
}
matrix tmp = {a, 1, b, 0}, ans, x = {1, 1, 0, 0};
ans = pow_matrix(tmp, n - 2);
// printf("ans:\n");
/*for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
printf("%lld ",ans.mat[i][j]);
}
printf("\n");
}*/
//printf("\n");
printf("%lld\n",(ans.mat[0][0]+ans.mat[1][0])%7);
}
return 0;
}