数列程序速度

Question

我有这个数字序列 - xm = y.xm-1 + z (mod 20 000)。

这些是限制： 1 ≤ x < 20 000, 0 ≤ y, z ≤ 9, 1 ≤ N ≤ 2 000 000 00 这是我的 [code][1].

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

double k =0;
int x,y,z;
unsigned long long n;

int solve()
{
    int result = 0;
    int prevX = x;
    for(unsigned long long i =1; i<n; i++)
    {
        if(result<20000)
        {
            result = y * prevX+z;
            prevX = result;

        }
        else
        {
             result = y * prevX+z;
             result = result % 20000;
             prevX = result;

        }

    }
    return result;
}

int main()
{
int tests =0;
cin >> tests;
cin.ignore();
 while(tests--)
    {
    scanf("%d %d %d %Ld", &x, &y, &z, &n);
    int result = solve();
    cout << result;
    }

}

示例输入： 1个 2 3 4 10

示例输出： 18730

详情：第一行的1是输入测试的编号。

2 3 4 10 - x,y,z, N; 我正在使用的判断系统给我一个时间限制错误。所以我的程序很慢。

有什么方法可以预测这个数字序列，消除大部分循环吗？

Answer 1

你的解是线性的，因为你有一个从 0 到 N 的循环。你可以改为对数。

您可以根据经验得出方程式，通过一个简单的实验，只需插入一个数字，例如 m = 4。让我们暂时忽略模数部分，因为我们可以只对最终数字执行此操作（参见示例 https://en.wikipedia.org/wiki/Modular_arithmetic#Integers_modulo_n）。

x[4] = y * x[3] + z
     = y * (y * x[2] + z) + z
     = y^2 * x[2] + y * z + z
     = y^2 * (y * x[1] + z) + y * z + z
     = y^3 * x[1] + y^2 * z + y * z + z

所以你很容易得到规则，如果你不会，从m = 5开始。它是：

x[m] = y^(m-1) * x[1] + y^(m-2) * z + ... + y^0 * z
     = y^(m-1) * x[1] + z * (y^(m-2) + ... + y^0)

观察，这是一个geometric series，即

x[m] = y^(m-1) * x[1] + z * (y^(m-1) - 1) / (y - 1) mod 20000

所以剩下的就是计算 y^(m-1)，您可以在 log m 中轻松完成。

在所有步骤中请注意取模规则！即，如果您计算 y * y mod 20000，则改为计算 (y mod 20000) * (y mod 20000) mod 20000。

例子

让我们取z = 10、y = 11、x[1] = 3，然后你有

    x[2] = 11 * 3 + 10 mod 20000 = 43
    x[3] = 11 * 43 + 10 mod 20000 = 483
    x[4] = 11 * 1850 + 10 mod 20000 = 5323
    x[5] = 11 * 460 + 10 mod 20000 = 58563 mod 20000 = 18563

或者直接获取：

    x[5] = 11^4 * 3 + 10 * (11^4 - 1) / (11 - 1) mod 20000
         = 14641 * 3 + 10 * (14641 - 1) / 10 mod 20000
         = 43923 + 14640 mod 20000
         = 644204 mod 20000
         = 18563

请记住，如果 y == 19284，请将四次方计算为 (y^2 mod 20000)^2 mod 20000 = 12656^2 mod 20000 = 14336，以确保不会溢出。

数列程序速度

Number sequence program speed

c++

sequence

例子