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}

• 所以這個狀態空間是有限的, 最大不超過49

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

• 然後列舉這個週期的全體, 找到和f(n)處於週期中相同位置的那個數

補充:

• 你程式碼中q不是最短週期, 其實可以在找到第一個週期時停下

• 當n是49的倍數時一定回傳f[0]=0 這可能是個bug