BSGS模板

求解：

博客

code:

const int maxn=(1<<16)-1;
struct HASH{
    int v[maxn+1],tot,ed=0;
    struct node{
        int t,p,next;
    }a[maxn<<1];
    void ins(int x,int y) {
        int k=x&maxn;
        if(v[k]!=ed) {
            v[k]=ed;
            a[k].t=x,a[k].p=y,a[k].next=0;
        }
        else {
            for(;;k=a[k].next) {
                if(a[k].t==x) return a[k].p=y,void();
                if(!a[k].next) break;
            }
            a[k].next=++tot,a[tot].t=x,a[tot].p=y,a[tot].next=0;
        }
    }
    int find(int x) {
        int k=x&maxn;
        if(v[k]!=ed) return -1;
        for(;;k=a[k].next)
            if(a[k].t==x) return a[k].p;
            else if(!a[k].next) return -1;
    }
}mp;
int bsgs(int a,int b,int p) {
    if(!a) {
        if(!b) return 1;
        else return -1;
    }
    if(b==1||p==1) return 0;
    mp.tot=maxn;
    int m=ceil(sqrt(p));
    ll tmp=1,s=1;
    for(int j=0; j<m; ++j)
        mp.ins(tmp*b%p,j),tmp=tmp*a%p;
    for(int i=1; i<=m; ++i) {
        s=s*tmp%p;
        if(~mp.find(s)) return i*m-mp.find(s);
    }
    return -1;
}

求解：

博客

code:

const int maxn=(1<<16)-1;
struct HASH{
    int v[maxn+1],tot,ed=0;
    struct node{
        int t,p,next;
    }a[maxn<<1];
    void ins(int x,int y) {
        int k=x&maxn;
        if(v[k]!=ed) {
            v[k]=ed;
            a[k].t=x,a[k].p=y,a[k].next=0;
        }
        else {
            for(;;k=a[k].next) {
                if(a[k].t==x) return a[k].p=y,void();
                if(!a[k].next) break;
            }
            a[k].next=++tot,a[tot].t=x,a[tot].p=y,a[tot].next=0;
        }
    }
    int find(int x) {
        int k=x&maxn;
        if(v[k]!=ed) return -1;
        for(;;k=a[k].next)
            if(a[k].t==x) return a[k].p;
            else if(!a[k].next) return -1;
    }
}mp;
int gcd(int a,int b) {
    if (a<b) return gcd(b,a);
    if (!b) return a;
    return gcd(b,a%b);
}
int bsgs(int a,int b,int p,int na) {
    if(!a) {
        if(!b) return 1;
        else return -1;
    }
    if(b==na||p==1) return 0;
    mp.tot=maxn;
    int m=ceil(sqrt(p));
    ll tmp=1,s=na;
    for(int j=0; j<m; ++j)
        mp.ins(tmp*b%p,j),tmp=tmp*a%p;
    for(int i=1; i<=m; ++i) {
        s=s*tmp%p;
        if(~mp.find(s)) return i*m-mp.find(s);
    }
    return -1;
}
int exbsgs(int a,int b,int p) {
    if(b==1||p==1) return 0;
    int g=gcd(a,p),k=0,na=1;
    while(g>1) {
        if(b/g*g!=b) return -1;
        ++k,p/=g,b/=g,na=1LL*na*(a/g)%p,g=gcd(a,p);
        if(na==b) return k;
    }
    int x,y,res;
    res=bsgs(a,b,p,na);
    if(res==-1) return -1;
    else return res+k;
}
signed main() {
    int a,p,b;
    while(cin>>a>>p>>b) {
        if(!a&&!p&&!b) return 0;
        a%=p,b%=p,++mp.ed;
        int x=exbsgs(a,b,p);
        if(~x) cout<<x<<'\n';
        else cout<<"No Solution\n";
    }
    return 0;
}

求解：

求出的所有解。

博客