1005 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

Solution:

这题还没有过.

递归法

先根据给出的公式, 实现了一种递归的写法, 但是MLE了, 栈溢出了吧。

#include <cstdio>

int f(int n, int a, int b) {
  if (n == 1 || n == 2) return 1;
  return (a * f(n-1, a, b) + b * f(n-2, a, b)) % 7;
}

int main() {
  int a, b, n;
  while (scanf("%d %d %d", &a, &b, &n) != EOF && a && b && n) {
    printf("%d\n", f(n, a, b));
  }
  return 0;
}

// MLE

迭代法

改成另外一种迭代法, 虽然不会造成栈溢出, 但TLE, 因为题目中1 <= n <= 100,000,000, 肯定会超时.

#include <cstdio>

int main() {
  int a, b, n;
  while (scanf("%d %d %d", &a, &b, &n) != EOF && a && b && n) {
    long long int fa = 1;          // f2
    long long int fb = (a+b) % 7;  // f3
    long long int ft = 0;
    int k = n - 3;
    while (k--) {
      ft = fb;
      fb = (a*fb + b*fa) % 7;
      fa = ft;
    }
    printf("%lld\n", fb);
  }
  return 0;
}

打表法

打表, 求余; 还不是很理解.

1, 因为余数是7, f(n)在0~6之间, 根据f(1), f(2)知道, 重新回到1, 1说明是一个周期, 所以两两配对, 一个7个数据, 49种可能.
2, 既然是49种可能, 那么n % 49的余数肯定小于49, 所以利用for循环, 将f(n)的数据都存入seq数组中, 复杂度很低.

#include <cstdio>
int main() {
  int a, b, n;
  while (scanf("%d %d %d", &a, &b, &n)) {
    int i;
    int seq[1000] = {0};
    seq[1] = 1;
    seq[2] = 1;
    int t;
    if (a == 0 && b == 0 && n == 0) {
      break;
    }
    for (i = 3; i <= 49; i++) {
      seq[i] = (a * seq[i-1] + b * seq[i-2]) % 7;
    }
    t = n % 49;
    printf("%d\n", seq[t]);
  }
  return 0;
}

最后一种, 参考: https://blog.csdn.net/w_linux/article/details/75449891