如何在这个答案中理解"q = i - 4;"的代码？

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

码

#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]) //here too
                {
                    q = i - 4; //I can't catch the point
                }
            }
        }
        cout << f[n % q] << endl;

    }
    return 0;
}

Answer 1

鉴于f(n)完全由f(n - 1)和决定,f(n - 2)并且any f(x)是从0到6的整数,只有7*7 = 49的f(n - 1)和的组合f(n - 2).这意味着f(x)是周期性的,最长期限为49.一旦我们知道了这个时期,计算f(n)就像f(n % period)我们计算的一样容易f(0)..f(48).确切的时间取决于A和B,需要进行计算.为了计算周期,我们只需要找到两个连续值的重复f.也就是说,if f(x) == f(y) && f(x + 1) == f(y + 1),则|y - x|是它的周期f或整数倍.请注意,f(n) == f(n % (k*period))效果一样好f(n) == f(n % period).因此,在所讨论的代码中,q它是一个周期f或整数倍.

现在,为什么代码预先计算f(0)..f(53)而不是f(0)..f(48)？我认为这是一种矫枉过正,因为超出最长时期的两个额外元素就足够了.

关于有问题的代码的另一个令人不安的事情是,这f[0]是一个假值,如果n是一个倍数,可能会被返回q.这可能是一个错误.为了防止它发生,我会将索引转换为f1,f(0) == 1 && f(1) == 1而不是f(1) == 1 && f(2) == 1.

Answer 2

是的,这种问题应该是OnlineJudge(OJ)的一个问题.也许你是ACM的新手？

Blew是我的答案:

所有这个解决方案可以工作的原因是因为mod 7,这意味着答案只能是0,1,2,3,4,5,6.所以,这个问题只能从3到54循环,因为这就足够了.怎么说,因为f [n]只用f [n-1]和f [n-2]之前的两个值确定,f [n-1]有7个选择(0-6)所以f [ N-2].

所以具有更多49的循环就足够了,当一些f [n-1]和f [n-2]等于f [4]和f [3]时,以下值将是循环.

以你的第二个例子为例.

f[1] = 1
f[2] = 1
A = 1
B = 2
n = 10 // or set n larger.

我们将得到

f[3] = 3
f[4] = 5
f[5] = 4
f[6] = 0
f[7] = 1
f[8] = 1
f[9] = 3
f[10] = 5
f[11] = 4

为f[9] == f[3]和f[10] == f[4],那么它将循环再后的数字,4, 0, 1, 1, 3, 5,

因此q = i - 4删除了前四个数字,因为它n%q是循环序列中第n个数字的位置.

我想知道我是否清楚地说明了答案,希望这对你有所帮助.