526互联

扩展BSGS/exBSGS算法

发布时间 2023-07-05 09:11:10作者: reclusive2007

上一篇博客提到，BSGS算法是用来解决形如：\(a^{x}\equiv b\pmod{p}\) 的高次同余方程。其中 \(a\perp p\)。

那如果 \(a\) 与 \(b\) 不互质，阁下又该如何应对呢？

exBSGS算法就是来解决形如：\(a^{x}\equiv b\pmod{p}\) 的高次同余方程。其中 \(a\) 不一定与 \(p\) 互质。

问题：

P4195 【模板】扩展 BSGS/exBSGS

给定整数 \(a,b,p\)，求满足的 \(a^{x}\equiv b\pmod p\) 最小非负整数解 \(x\)。

解决：

首先，既然我们会求 \(a\perp p\) 的情况，那我们就将原问题转化为 \(a\perp p\) 的情况。

令 \(d_1=\gcd(a,p)\)，由裴蜀定理可知，若 \(d_1\nmid b\)，则原方程无解。

否则的话，方程两边同时除以 \(d_1\)，原方程化为：\(\frac{a}{d_1} a^{x-1} \equiv \frac{b}{d_1} \pmod{\frac{p}{d_1}}\)。

若 \(a\) 与 \(\frac{p}{d_1}\) 仍然不互质，则令 \(d_2=\gcd(a,\frac{p}{d_1})\)，若 \(d_2 \nmid \frac{b}{d_1}\)，则原方程无解。

否则的话，方程两边同时除以 \(d_2\)，原方程化为：\(\frac{a^2}{d_1 d_2} a^{x-2} \equiv \frac{b}{d_1 d_2} \pmod{\frac{p}{d_1 d_2}}\)

一直执行下去，直到 \(a\mid \frac{p}{d_1...d_k}\)，令 \(d=\prod_{i=1}^k d_i\)，

原方程化为：\(\frac{a^k}{d} a^{x-k} \equiv \frac{b}{d} \pmod{\frac{p}{d}}\),

由于 \(a\mid \frac{p}{d_1...d_k}\)，则原方程可以用BSGS来解决。

接下来参考BSGS算法这篇博客。

记得最后求出的是 \(x-k\)，要加回 $$k。

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b){
    if(!a)return b;
    return gcd(b%a,a);
}
LL exBSGS(LL a,LL b,LL p){
    a%=p,b%=p;
    if(b==1||p==1)return 0;
    LL d,k=0,A=1;
    while(1){
        d=gcd(a,p);
        if(d==1)break;
        if(b%d!=0)return -1;
        k++,b/=d,p/=d;
        A=A*(a/d)%p;
        if(A==b)return k;
    }
    LL m=ceil(sqrt(p)),t=b;
    unordered_map<int,int>Hash;
    Hash[b]=0;
    for(int j=1;j<m;j++){
        t=t*a%p;
        Hash[t]=j;
    }
    LL mi=1;
    for(int i=1;i<=m;i++)mi=mi*a%p;
    t=A;
    for(int i=1;i<=m;i++){
        t=t*mi%p;
        if(Hash.count(t))return i*m-Hash[t]+k;
    }
    return -1;
}
int main(){
    LL a,b,p;
    while(scanf("%lld%lld%lld",&a,&p,&b)!=EOF&&a&&p&&b){
        LL ans=exBSGS(a,b,p);
        if(ans==-1)puts("No Solution");
        else printf("%lld\n",ans);
    }
    return 0;
}