2019牛客多校第5场 generator 2 （BSGS）

题意

$X_i=a\cdot X_{i-1}+b\left(modp\right)$Xi​=a⋅Xi−1​+b  (mod  p)
给出 $X_0$X0​，序列长度 $n,a,b,p$n,a,b,p 的值，求 $X_k=V$Xk​=V 的最小的 $k$k ,没有则输出 $-1$−1

题解

$\begin{array}{cc}{\displaystyle X_n}& {\displaystyle =X_0\cdot a^n+a^{n-1}b+a^{n-2}b+...+b}\\ {\displaystyle }& {\displaystyle =X_0\cdot a^n+b\frac{1-a^n}{1-a}}\\ {\displaystyle }& {\displaystyle =V}\end{array}$Xn​​=X0​⋅an+an−1b+an−2b+...+b=X0​⋅an+b  1−a1−an​=V​
$V=X_0\cdot a^n+b\frac{1-a^n}{1-a}V=X_0\cdot a^n+b^{\prime }(a^n-1)a^n=\frac{V+b^{\prime }}{X_0+b^{\prime }}{a}^n=V^{\prime }$V=X0​⋅an+b  1−a1−an​V=X0​⋅an+b′ (an−1)an=X0​+b′V+b′​an=V′
然后用 $BSGS$BSGS 求即可
直接求得话会 $TLE$TLE， 因为询问太多了，需要预处理
$a^n=a^{p\cdot m-b}$an=ap⋅m−b
$a^{p\cdot m}\cdot (V^{\prime }{)}^{-1}=a^b$ap ⋅m⋅(V′)−1=ab
考虑预处理出 $m=1e6$m=1e6 时的 $a$a 的幂，即 $b\in [0,1000000)$b∈[0,1000000)
然后枚举 $p$p , 再 $Hash$Hash 查找即可

代码

#include<bits/stdc++.h>
#define N 1000010
#define INF 0x3f3f3f3f
#define eps 1e-5
#define pi 3.141592653589793
#define mod 998244353
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
   
int m,T;
LL x,a,b,p,n,v;
   
LL qpow(LL a,LL b){
    LL res=1;
    while(b){
        if (b&1) res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
  
struct HASH
{
    const int M = 1999997;
    int la[2000000],nx[2000000],cc[N],key[N],cnt=0;
    void clr(){
        memset(la,-1,sizeof la);
        cnt=0;
    }
    inline int find(int x){
        int h=x%M;
        for (int i=la[h];i!=-1;i=nx[i])
            if (key[i]==x) return cc[i];
        return  -1;
    }
    inline void ins(int x,int w){
        int h=x%M;
        key[++cnt]=x;
        cc[cnt]=w;
        nx[cnt]=la[h];
        la[h]=cnt;
    }
}mp;
 
void slove(){
    b=b*qpow(a-1,p-2)%p;
    LL tm=qpow(b+x,p-2),t=1;
    int block=pow(p,2.0/3);
    mp.clr(); mp.ins(1,1);
    for(int i=1;i<block;i++) t=t*a%p,mp.ins(t,i+1);
    a=qpow(a,block);
    int lim=min(p/block,n/block)+1;
    while(m--){
        scanf("%lld",&v);
        if (x==v) { puts("0");continue; }
        v=(v+b)%p*tm%p;
        if (v==1) { puts("0");continue; }
        LL iv=qpow(v,p-2);
        LL res=1; int fg=0;
        for(int i=1;i<=lim;i++){
            res=res*a%p;
            int t=mp.find(res*iv%p);
            if (t!=-1) {
                LL pos=i*block-t+1;
                if (pos<n){
                    printf("%lld\n",pos);
                }else puts("-1");
                fg=1;
                break;
            }
        }
        if (!fg)puts("-1");
    }
}
   
void fix0(){
    while(m--){
        scanf("%lld",&v);
        if (v==x) puts("0");else
        if (v==b) puts("1");else puts("-1");
    }
}
void fix1(){
    int ib=qpow(b,p-2);
    while(m--){
        scanf("%lld",&v);
        if (b==0){
            if (v==x) puts("0");else puts("-1");
            continue;
        }
        LL pos=(v-x+p)%p*ib%p;
        if (pos<n) printf("%lld\n",pos);else puts("-1");
    }
}
  
int main(){
    sc(T);
    while(T--){
        scanf("%lld%lld%lld%lld%lld",&n,&x,&a,&b,&p);
        sc(m);
        if (a==0) fix0();else
        if (a==1) fix1();else
        slove();
    }
}