【文文殿下】【SDOI2013】随机数生成器 题解

题意

给你个随机数生成器 \(f(x) = a*f(x-1)+b (\mod p)\)，给你初始信息\(a,b,t,p,f(1)\)，问你几次等于\(t\)，如果不等于输出\(-1\).

题解

\[f(n) = a*f(n-1)+b\]

\[f(n) = c*a^{n-1} + \frac {b(a^n-1)}{a-1} \text { where c is an arbitrary parameter} \]

不过上面这个式子咱推不出来，考虑矩阵乘法

\[\begin{pmatrix} a&b\\ 0&1 \end{pmatrix}^x \times \begin{pmatrix} f(1)\\ 1 \end {pmatrix} = \begin{pmatrix} t\\ 1 \end{pmatrix}\]

我们考虑一个BSGS用到矩阵上，就把他做了。
如果你要用这个式子的话
\[a^{i\sqrt{p} + k} = b (\mod p) \]
前面那个转移矩阵的逆矩阵是
\[\begin{pmatrix} \frac{1}{a}&-\frac{b}{a}\\ 0&1 \end{pmatrix} \]

但我懒得用用逆矩阵，直接用下面的这个式子。
\[a^{i\sqrt{p} - k} = b (\mod p) \]

带了矩阵常数贼大，我还懒得手写hashtable，吸着氧过了。
估计思路这么清(zhi)奇(zhang)的人没几个吧。

#include<bits/stdc++.h>
using namespace std;
int p;
int inc(int a,int b) {
    a+=b;
    return a>=p?a-p:a;
}
int dec(int a,int b) {
    a-=b;
    return a<0?a+p:a;
}
int mul(int a,int b) {
    return 1LL*a*b%p;
}
struct qwq {
    int r,c;
    int a[3][3];
    qwq(){
        memset(a,0,sizeof a);
        r=c=0;
    }
    qwq operator * (const qwq& rhs) const {
        qwq ret;
        ret.r = r,ret.c = rhs.c;
        for(int i=1;i<=r;++i) {
            for(int j=1;j<=rhs.c;++j) {
                for(int k=1;k<=c;++k) {
                    ret.a[i][j]=inc(ret.a[i][j],mul(a[i][k],rhs.a[k][j]));
                }
            }
        }
        return ret;
    }
    bool operator < (const qwq& rhs) const {
        if(r!=rhs.r) return r<rhs.r;
        if(c!=rhs.c) return c<rhs.c;
        for(int i=1;i<=r;++i)
            for(int j=1;j<=c;++j)
                if(a[i][j]!=rhs.a[i][j])
                    return a[i][j]<rhs.a[i][j];
        return 0;
    }
};
int T,a,b,x1,t,ans;
qwq qpow(qwq a,int b) {
    assert(b>=0);
    qwq ret;
    ret.r=a.r,ret.c=a.c;
    for(int i=1;i<=ret.r;++i) ret.a[i][i]=1;
    while(b) {
        if(b&1) ret=ret*a;
        a = a * a;
        b>>=1;
    }
    return ret;
}
bool BSGS(void) {
    map<qwq,int> M;
    M.clear();
    int lmt = sqrt(p)+1;
    ans = 0x3f3f3f3f;
    qwq base;
    base.a[1][1]=a,base.a[1][2]=b,base.a[2][2]=1;
    base.r=base.c=2;
    qwq fn;
    fn.r=2,fn.c=1;
    fn.a[1][1]=t,fn.a[2][1]=1;
    qwq st;
    st.r=2,st.c=1;
    st.a[1][1]=x1,st.a[2][1]=1;
    qwq step = qpow(base,lmt);
    for(int i=1;i<=lmt+1;++i) {
        st = step*st;
        if(!M.count(st)) {
            M[st]=i;
        }
    }
    bool flag = 0;
    for(int i=0;i<=lmt;++i) {
        if(i) fn = base*fn;
        if(M.count(fn)) {
            flag = 1;
            ans = min(ans,M[fn]*lmt-i);
        }
    }
    return flag;
}
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d%d%d%d",&p,&a,&b,&x1,&t);
        if(a==0) {
            if(x1==t)
                puts("1");
            else {
                if(b==t) {
                    puts("2");
                }
                else {
                    puts("-1");
                }
            }
        }
        else {
            if(BSGS()) {
                printf("%d\n",ans+1);
            }
            else {
                puts("-1");
            }
        }
    }
    return 0;
}