題目
Number Sequence
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
題目描述
題目的意思是，給出整數(shù)A,B和n暗挑，利用公式
算出f(n)的值队萤。
題目解法
一開始是用簡單的模擬來做這一題淹朋，結(jié)果提交后是超時；由于給出的n可能很大是會造成超時的原因昏苏。在上網(wǎng)搜索后肴盏，用了矩陣快速冪這種方法，來降低時間抱环。矩陣快速冪是利用矩陣的乘法公式壳快，將遞推式化成下圖的形式，這樣問題就變成了镇草，如何快速求前者矩陣的n-2次冪眶痰。
在求某個數(shù)的n次冪問題中，可以利用數(shù)論中的快速冪技巧梯啤。如果用最直白的方法算a^168竖伯，在程序中則需要做167次的乘法；168=128+16+4因宇，如果將168轉(zhuǎn)成二進(jìn)制的話就是：10010100七婴，
這是，只需算8*3=24次運算即可完成察滑；下圖是快速冪的代碼打厘，主要可以利用base的增長是以二進(jìn)制數(shù)值形式的增長，即是從a贺辰、a^2户盯、a^4、a^8.....這種形式增長下去饲化。這種快速冪的技巧莽鸭，在矩陣中也可以使用。
題目代碼
const int N = 3;
struct Mat{
int mat[N][N];
};
Mat operator * (Mat a, Mat b) {
? Mat c;
? int i, j, k;
? memset(c.mat, 0, sizeof(c.mat));
? for (i = 0; i < 2; i++)
? ? ?for (j = 0; j < 2; j++)
? ? ? ?for (k = 0; k < 2; k++) {
? ? ? ?c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
? ? ? ?c.mat[i][j] %= 7;
? ? ? ?}
? return c;
? }
Mat operator ^ (Mat a, int b) {
? Mat c;
? int i, j;
? for (i = 0; i < 2; i++)
? ? ?for (j = 0; j < 2; j++)
? ? ? ?c.mat[i][j] = (i == j);
? while(b != 0) {
? if (b & 1 != 0)
? ? ? c = c * a;
? ? a = a * a;
? b /= 2;
? }
? return c;
? }
int main() {
int a, b, n;
Mat matrix, result;
while (scanf("%d %d %d", &a, &b, &n) && (a || b || n)) {
if (n == 1 || n == 2) {
printf("1\n");
continue;
}
matrix.mat[0][0] = a % 7; matrix.mat[0][1] = b % 7;
matrix.mat[1][0] = 1;? matrix.mat[1][1] = 0;
result = matrix^(n - 2);
printf("%d\n", (result.mat[0][0] + result.mat[0][1]) % 7);
}
return 0;
}
