模板——EXBSGS-程序员宅基地

\(hash\)版，省时间耗空间

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

typedef long long LL;
const LL N=40000,Max=(1<<16)-1;
bool bk;
LL X,Z,K,len;
bool vis[70000];
struct node{
    LL d,id,next;
}hash[2*Max];

int exgcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0) {x=1,y=0;return a;}
    LL tx,ty;
    LL d=exgcd(b,a%b,tx,ty);
    x=ty;y=tx-(a/b)*ty;
    return d;
}

void ins(LL d,LL id)
{
    LL t=d&Max;
    if(!vis[t]) {
        vis[t]=1;
        hash[t].d=d,hash[t].id=id,hash[t].next=-1;
        return ;
    }
    for(;hash[t].next!=-1;t=hash[t].next)
    {
        if(hash[t].d==d) return;
    }
    hash[t].next=++len;
    hash[len].d=d;hash[len].id=id;hash[len].next=-1;
}

LL find(LL d)
{
    LL t=d&Max;
    if(!vis[t]) return -1;
    for(;t!=-1;t=hash[t].next)
    {
        if(hash[t].d==d) return hash[t].id;
    }
    return -1;
}

LL BSGS()
{
    LL t,g,x,y,pm,a,b,c,m,k,sum,am;
    a=X;b=K;c=Z;k=1;sum=0;t=1%c;
    for(int i=0;i<=100;i++){
        if(t==b) return i;
        t=t*a%c;
    }
    while((g=exgcd(X,c,x,y))!=1)
    {
        k=(k*X/g)%c;
        c/=g;
        if(b%g) return -1;
        b/=g;
        sum++;
    }
    m=(LL)(ceil((double)sqrt((double)c)));
    ins(k,0);
    t=k;pm=1;
    for(int i=1;i<=m;i++)
    {
        t=t*a%c,pm=pm*a%c;
        ins(t,i);
    }        
    exgcd(pm,c,x,y);
    am=x%c+c;
    t=b;
    for(int i=0;i<=m;i++)
    {
        x=find(t);
        if(x!=-1) return i*m+x+sum;
        t=t*am%c;
    }
    return -1;
}

int main()
{
    while(~scanf("%lld%lld%lld",&Z,&X,&K)){
        K%=Z;len=Max;
        memset(vis,0,sizeof(vis));
        LL ans=BSGS();
        if(ans!=-1) printf("%lld\n",ans);
        else printf("no solution!\n");
    }
    return 0;
}

二分版，耗时间省空间

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

typedef long long LL;
const int N=40000;
bool bk;
LL X,Z,K,a,b,c,m,k,sum,am,bl;
struct node{
    LL d,id;
}bit[N],p[N];

bool cmp(node x,node y){
    if(x.d!=y.d) return x.d<y.d;
    return x.id<y.id;
}

LL gcd(LL u,LL v)
{
    if(v==0) return u;
    return gcd(v,u%v);
}

LL find(LL x)
{
    int l=0,r=bl;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(bit[mid].d==x) return bit[mid].id;
        if(bit[mid].d>x) r=mid-1;
        if(bit[mid].d<x) l=mid+1;
    }
    return -1;
}

void exgcd(LL u,LL v,LL &x,LL &y)
{
    if(v==0) {x=1,y=0;return ;}
    LL tx,ty;
    exgcd(v,u%v,tx,ty);
    x=ty;y=tx-(u/v)*ty;
    return;
}

LL BSGS()
{
    LL t,g,x,y,pm;
    a=X;b=K;c=Z;k=1;sum=0;bk=1;bl=0;t=1%c;
    for(int i=0;i<=100;i++){//避免a的负数次方
        if(t==b) return i;
        t=t*a%c;
    }
    while((g=gcd(X,c))!=1)
    {
        k=(k*X/g)%c;//k记得要mod，否则溢出
        c/=g;
        if(b%g) return -1;
        b/=g;
        sum++;
    }
    m=(LL)(ceil((double)sqrt((double)c)));//要约分之后再求m
    p[0].d=k%c;
    p[0].id=0;
    pm=1;//pm是不用*k的
    for(int i=1;i<=m;i++) 
        p[i].d=p[i-1].d*a%c,pm=pm*a%c,p[i].id=i;
    sort(p,p+1+m,cmp);
    bit[0]=p[0];bl=0;
    for(int i=1;i<=m;i++)
    {
        if(p[i].d!=p[i-1].d) bit[++bl]=p[i];
    }
    exgcd(pm,c,x,y);
    am=(x%c+c);//避免am=0
    
    t=b;
    x=find(b);
    if(x!=-1) return x;
    for(int i=1;i<=bl;i++)
    {
        t*=am;t%=c;
        x=find(t);
        if(x!=-1)
            return i*m+x;
    }
    return -1;
}

int main()
{
//     freopen("exbsgs10.in","r",stdin);
//     freopen("exbsgs10.out","w",stdout);
    while(~scanf("%lld%lld%lld",&Z,&X,&K)){
        if(!X && !Z && !K) return 0;
        K%=Z;
        LL ans=BSGS();
        if(ans!=-1) printf("%lld\n",ans+sum);
        else printf("no solution!\n");
    }
    return 0;
}