BSGS求解离散对数问题

离散对数问题是求解a^xΞb mod(n) 同余方程

以下模板使用于gcd(a,n)=1的情况

const int mod = 76543;
int hs[mod],head[mod],Next[mod],id[mod],top;
void insert(int x,int y){
    int k=x%mod;
    hs[top]=x,id[top]=y,Next[top]=head[k],head[k]=top++;
}
int find(int x){
    int k=x%mod;
    for(int i=head[k];i!=-1;i=Next[i])
    if(hs[i]==x) return id[i];
    return -1;
}
int BSGS(int a,int b,int n){
    memset(head,-1,sizeof(head));
    top=1;
    if(b==1) return 0;
    int m=sqrt(n*1.0+1),j;
    long long x=1,p=1;
    for(int i=0;i<m;++i,p=p*a%n)
    insert(p*b%n,i);
    for(long long i=m;;i+=m){
        if((j=find(x=x*p%n))!=-1) return i-j;
        if(i>n) break;
    }
    return -1;
}