数字顺序程序速度

问题描述 投票:0回答:1

我有这个数字序列-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;我使用的判断系统给我一个时间限制错误。所以我的程序很慢。

有没有办法预测这个数字序列,从而消除大部分循环?

c++ sequence
1个回答
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 = 10y = 11x[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,以确保不会溢出。

热门问题
推荐问题
最新问题