数字顺序程序速度

Question

我有这个数字序列-xm = y.xm-1 + z（mod 20000）。

这些是限制：1≤x <20 000，0≤y，z≤9，1≤N≤2000000这是我的[代码] [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，以确保不会溢出。