How to understand this code in OJ's answer?-PHP Chinese Network Q&A

Article Topic Learning Download Q&A Programming Dictionary Game Recent Updates

简体中文(ZH-CN) English(EN) 繁体中文(ZH-TW) 日本語(JA) 한국어(KO) Melayu(MS) Français(FR) Deutsch(DE)

How to understand this code in OJ's answer?

漂亮男人 2017-06-24 09:42:59

909

Problem Description

A number sequence is defined as follows:

f(1) = 1, f(2) = 1, f(n) = (Af(n - 1) Bf(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  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; }

漂亮男人

reply all (2)

给我你的怀抱2017-06-24 09:44:59 2 floor

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.

Like+0

Add Reply

曾经蜡笔没有小新2017-06-24 09:44:59 1 floor

The following discussions are limited toi>=1:

Obviouslyf(i) in { 0 .. 6}
SoThis state space is limited, the maximum does not exceed 49
Sof(i)has a period, and 49 is a period
Then enumerate the entire cycle and find the numberthat 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 returnf[0]=0This may be a bug

Like+0

Add Reply