# 数字顺序程序速度

##### 问题描述投票：0回答：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;
}

}
``````

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

c++ sequence
##### 1个回答
1

``````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
``````

``````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)
``````

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

# 示例

``````    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`，以确保不会溢出。