How to understand this code in OJ's answer?

Question

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

#include <iostream>
using namespace std;
int f[54] = {0, 1, 1};
int main()
{
    int A, B, n, q = 1;
    while (cin >> A >> B >> n && A && B && n)
    {
        for (int i = 3; i < 54; ++i)
        {
            f[i] = (A * f[i - 1] + B * f[i - 2]) % 7;   //这里
            if (i > 4)
            {    if (f[i - 1] == f[3] && f[i] == f[4])
                {
                    q = i - 4; //特别是这个地方

                }
            }
        }
        cout << f[n % q] << endl;  //这里

    }

    return 0;
}

Answer 1

Aren’t there problem-solving reports online? This question is looking for patterns. The q in this question is looking for the period T. As for why we only look for the first 54, this requires rigorous mathematical reasoning. I tested it and found that 53 is OK, but not below 52.

--------------Digression-------------

For this kind of question, at first glance, it’s like making a table or looking for patterns.

Under the premise that this question is not a wrong question, there are definitely two ways to solve this kind of question: violent table making or finding patterns. The former means that this question is a big question, and the latter means that this question is a reasoning question, right? Water depends on the difficulty of reasoning, but as far as this question is concerned, it is a big water problem. Just look at the problem-solving reports on the Internet. Some people directly open the array to 1000 until they find the period and jump out.

Answer 2

The following discussions are limited to i>=1:

• Obviously f(i) in { 0 .. 6}

• So<f(i-2), f(i-1)>This state space is limited, the maximum does not exceed 49

• So f(i) has a period, and 49 is a period

• Then enumerate the entire cycle and find the number that is at the same position in the cycle as

  f(n)

Added:

• q in your code is not the shortest period. In fact, you can stop when you find the first period

• When n is a multiple of 49, it must return f[0]=0 This may be a bug