题目

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

---

题目描述

题目的意思是，给出整数A,B和n，利用公式

算出f(n)的值。

题目解法

一开始是用简单的模拟来做这一题，结果提交后是超时；由于给出的n可能很大是会造成超时的原因。在上网搜索后，用了矩阵快速幂这种方法，来降低时间。矩阵快速幂是利用矩阵的乘法公式，将递推式化成下图的形式，这样问题就变成了，如何快速求前者矩阵的n-2次幂。

在求某个数的n次幂问题中，可以利用数论中的快速幂技巧。如果用最直白的方法算a^168，在程序中则需要做167次的乘法；168=128+16+4，如果将168转成二进制的话就是：10010100，

这是，只需算8*3=24次运算即可完成；下图是快速幂的代码，主要可以利用base的增长是以二进制数值形式的增长，即是从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;

}

---