扩展 BSGS

luckydrawbox · 2022-08-12 07:59:43 · 个人记录

函数

代码

long long qmi(long long a,long long b,long long c){
    long long ans=1;
    while(b){
        if(b&1)
            ans=ans*a%c;
        a=a*a%c;
        b>>=1;
    }
    return ans;
}
ll gcd(ll a,ll b){
    return b?gcd(b,a%b):a;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1;y=0;
        return a;
    }
    ll d=exgcd(b,a%b,x,y);
    ll z=x;x=y;y=z-a/b*x;
    return d;
}
map<int,int>ahash;
int Baby_Step_Giant_Step(int a,int b,int p){
    ahash.clear();
    b%=p;
    int t=(int)sqrt(p)+1,val=b;
    for(int j=0;j<t;j++){
        if(j)
        val=1ll*val*a%p; // b*a^j
        ahash[val]=j;
    }
    a=qmi(a,t,p); // a^t
    if(!a)
        return b?-1:1;
    for(long long i=0;i<=t;i++){
        val=qmi(a,i,p); // (a^t)^i
        int j=ahash.find(val)==ahash.end()?-1:ahash[val];;
        if(j>=0&&i*t-j>=0)
            return i*t-j;
    }
    return -1;
}
ll exBSGS(ll a,ll b,ll p){//a^x=b (mod p)
    a%=p;b%=p;
    if(b==1||p==1)
        return 0;
    ll cnt=0,s=1,t=1;
    for(ll i=0;i<=50;i++){
        if(t==b)
            return i;
        t=t*a%p;
    }
    bool f=0;
    while(1){
        ll d=gcd(a,p);
        if(d==1)
            break;
        if(b%d){
            return -1;
        }
        cnt++;
        b/=d;p/=d;
        s=s*(a/d)%p;
    }
    ll x,y;
    exgcd(s,p,x,y);
    b=b*(x%p+p)%p;
    ll ans=Baby_Step_Giant_Step(a,b,p);
    if(ans==-1)
        return ans;
    return ans+cnt;
}