c++ - 如何理解OJ答案中的这段代码？

Question

问题描述

数列定义如下：

f(1) = 1, f(2) = 1, f(n) = (A f(n - 1) + B f(n - 2)) mod 7.

给定 A、B 和 n，你要计算 f(n) 的值。

输入

输入由多个测试用例组成。每个测试用例
在一行中包含 3 个整数 A、B 和 n（1 <= A、B <= 1000、1
<= n <= 100,000,000）。三个零表示输入结束，这个
测试用例将不被处理。

输出

对于每个测试用例，在一行上打印 f(n) 的值。

示例输入

1 1 3

1 2 10

0 0 0

示例输出

2

5

雷雷

Answer 1

网上不是有解题报告么。这题找规律啊，这题的 q 就是在找周期 T 啊。至于为什么只找前54个，这需要数学严格的推理吧。我测试了下，53也行，52以下不可以。

--------------题外话-------------

这种题的话，一眼看过去就是 打表 或者 找规律。

在这题不是错题的前提下，这种题肯定无外乎两种解法：暴力打表 或 找规律 ，前者说明此题就是个大水题，后者说明这题是推理题，是不是水，看推理的难度，但就本题而言，大水题，看下网上的解题报告就知道了，有人直接把数组开到1000，直到找到周期，跳出。

Answer 2

以下讨论都限定i>=1:

• 显然f(i) in { 0 .. 6}

• 所以<f(i-2), f(i-1)>这个状态空间是有限的, 最大不超过49

• 所以f(i)是有周期的, 且49是一个周期

• 然后枚举出这个周期的全体, 找到和f(n)处于周期中相同位置的那个数

补充:

• 你代码中q不是最短周期, 其实可以在找到第一个周期时停下

• 当n是49的倍数时一定返回f[0]=0 这可能是个bug