洛谷3306 [SDOI2013]随机数生成器

题意

给出 $A,B,X_1,p,t$ ，数列 $X_i$ 满足递推式：

$$X_{i+1}\equiv A\times X_i+B\pmod p$$

求使 $X_i\equiv t\pmod p$ 成立的最小的 $i$ 。

题解

一般情况

列出来找下规律：

$$\begin{cases}X_2\equiv A\times X_1+B\pmod p \\X_3\equiv A^{2}\times X_1+A\times B+B\pmod p \\X_4\equiv A^{3}\times X_1+A^{2}\times B+A\times B+B\pmod p\end{cases}$$

得

$$X_i\equiv A^{i-1}\times X_1+B\times \dfrac{1-A^{i-1}}{1-A}\pmod p$$

题目即求

$$t\equiv A^{i-1}\times X_1+B\times \dfrac{1-A^{i-1}}{1-A}\pmod p$$

对上式进行化简，先去分母：

$$t\times (1-A)\equiv (1-A)\times A^{i-1}\times X_1+B\times (1-A^{i-1}) \pmod p$$

将 $A^{i-1}$ 放在等式左边：

$$(X_1-X_1\times A-B)\times A^{i-1}\equiv t-A\times t-B \pmod p$$

得：

$$A^{i-1}\equiv \dfrac{t-A\times t-B}{X_1-X_1\times A-B} \pmod p$$

这个式子就可以用 $\text{BSGS}$ 直接求解了。

特殊情况

不愧省选题

$X_1=t$

答案为 $1$ 。

需要判断这个的原因是：即便因 $A$ 或 $B$ 取值而无解，仍能找到这个答案。

$A=0$

显然

$$X_i\equiv B\pmod p \ , \ i\geq 2$$

因为 $X_1=t$ 已经判断过了，那么判断是否满足 $B=t$ 即可。

判断这个的原因是：等式左侧 $=0$ ，右侧显然不可能 $=0$ 。

$A=1$

将原式转化为

$$X_1+(i-1)\times B\equiv t\pmod p$$

可以用 $\text{exgcd}$ 求解。

需要注意的是：如果求得的解为 $0$ 就输出 $p$，因为 $i\geq 1$ 。

判断这个的原因是：上述化简过程的分母中出现了 $1-A$ 。

代码

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

ll p,A,B,x1,t,T;

inline ll qpow(ll x,ll y,ll ha)
{
    ll ans=1;
    while (y)
    {
        if (y&1) ans=ans*x%ha;
        y>>=1;
        x=x*x%ha;
    }
    return ans%ha;
}

inline ll bsgs(ll a,ll b,ll ha)
{
    if (a%ha==0 && b) return -1;
    if (b%ha==1) return 0;
    ll y=sqrt(ha-1)+1;
    map <ll,ll> mp;
    ll right=b%ha;
    for (ll i=0;i<y;i++)
    {
        mp[right]=i+1;
        right=right*a%ha;
    }
    ll once=qpow(a,y,ha),left=once;
    for (ll i=1;i<=y;i++)
    {
        if (mp[left]) return i*y-mp[left]+2; //ans+=1
        left=left*once%ha;
    }
    return -1;
}

ll exgcd(ll l,ll r,ll &x,ll &y)
{
    if (r==0)
    {
        x=1; y=0;
        return l;
    }
    ll ans=exgcd(r,l%r,y,x);
    y-=l/r*x;
    return ans;
}

inline ll inv(ll x,ll ha) { return qpow(x,ha-2,ha); }

signed main()
{
    T=read();
    while (T--)
    {
        p=read(); A=read(); B=read(); x1=read(); t=read();
        if (x1==t) puts("1");
        else if (A==0) puts(B==t ? "2" : "-1");
        else if (A==1)
        {
            if (B==0) { puts("-1"); continue; }
            ll a=B,b=p,c=t-x1+B,x=0,y=0;
            ll g=exgcd(a,b,x,y);
            if (c%g) { puts("-1"); continue; }
            b/=g; c/=g;
            x=(x*c%b+b)%b;
            printf("%lld\n",x ? x : p);
        }
        else
        {
            ll a=A,b=(((t-A*t-B)%p+p)%p)*(inv(((x1-x1*A-B)%p+p)%p,p)%p)%p;
            printf("%lld\n",bsgs(a,b,p));
        }
    }
    return 0;
}