设\left\{\begin{array}{lll}<br /> y_0 & = & A \\<br /> y_i & = &\alpha \cdot y_{i-1}^2 + \beta \cdot y_{i-1} + \gamma<br /> \end{array}\right.，则y_i \equiv x_i (mod M)。
　　证明：
当i=0时，y_0=x_0=A；
假设当i=k时成立，
∵x_k<M
∴y_k=pM+x_k (p\in N)
则\begin{array}{lll}<br /> y_{k+1} & = & \alpha \cdot y_k^2 + \beta \cdot y_k + \gamma \\<br /> ~ & = & \alpha \cdot (p^2 M^2+ 2 pMx_k+x_k^2) + \beta \cdot (pM+x_k) + \gamma \\<br /> ~ & \equiv & x_{k+1} (mod M)<br /> \end{array}
即，当i=k+1时也成立；
∴y_i \equiv x_i (mod M)
x_i = y_i mod M。
　　但是，y这个递推关系不会解……
　　faster_noi提出不用解这个递推关系，就用\left\{\begin{array}{lll}<br /> x_0 & = & A \\<br /> x_i & = & (\alpha \cdot x_{i-1}^2 + \beta \cdot x_{i-1} + \gamma) Mod M<br /> \end{array}\right.做，x_i最多有M种取值，会出现循环的，所以把循环结找出来就行了。
　　Submit 1: WA on 5。要求的x_k并不一定出现在循环结中，有可能出现在循环结之前(faster_noi提供)。
　　Submit 2: WA on 5。假设求到的循环结是x_i~x_j，那么x_k=x_{i+(k-i) mod (j-i+1) }。
　　Submit 3: WA on 39。x_k=x_{i+(k-i) mod (j-i+1) }是错误的，我本想用这个式子统一一下x_k处在循环结之前和循环结中的情形，但它做不到，因为没有i+(k-i) mod (j-i+1) = i+(k-i) = k。所以对于x_k处在循环结之前的情形，仍要单独处理。
　　Submit 4: AC。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

//AC
#include <iostream>
using namespace std;
 
int main()
{
    long x[1001];
    long A,alpha,beta,gamma,m,k;
    cin>>A>>alpha>>beta>>gamma>>m>>k;
    x[0]=A;
    if (k==0) cout<<x[0];
    else
    {
        long app[1000],i(1);
        fill(app,app+1000,-1);
        app[x[0]%=m]=0;
        for (;app[x[i]=(alpha*x[i-1]*x[i-1]+beta*x[i-1]+gamma)%m]<0;++i) app[x[i]]=i;
        if (k>=app[x[i]]) cout<<x[app[x[i]]+(k-app[x[i]])%(i-app[x[i]])];
        else cout<<x[k];
    }
    cout<<endl;
    return 0;
}