同余

同余

本章主要记录有关同余、费马小定理、欧拉定理、扩展欧几里得算法、裴蜀定理、乘法逆元、威尔逊定理、线性同余方程、中国剩余定理、扩展中国剩余定理、BSGS以及扩展BSGS的学习笔记。

由于内容复杂且关联较少，建议配备 ctrl+F 进行快乐食用。

正在继更ing

一、基础知识

这个板块着重介绍同余的基本知识，虽然多为数学竞赛内容，但也对信息学竞赛有不少帮助，定理和性质为拓展内容。

本部分参考《初等数论》进行撰写。

1.1\(\quad\)基本定义、定理与性质

定义1（同余）\(\quad\) 设 \(m\neq0\)。若 \(m\mid a-b\)，即 \(a-b=km\)，则称 \(m\) 为模，\(a\) 同于与 \(b\) 模 \(m\) 以及 \(b\) 是 \(a\) 对模 \(m\) 的剩余，记作 \[ a\equiv b\pmod{m} \tag{1} \] 不然，则称 \(a\) 不同余于 \(b\) 模 \(m\)，\(b\) 不是 \(a\) 对模 \(m\) 的剩余，记作 \(a\not\equiv b\pmod{m}\)

式 \((1)\) 称为模 \(m\) 的同余式，或简称同余式。

由于 \(m\mid a-b\) 等价于 \(-m\mid a-b\) ，所以同余式 \((1)\) 等价于

\[ a\equiv b\pmod{(-m)} \] 定理1\(\quad\) \(a\) 同余于 \(b\) 模 \(m\) 的充要条件是 \(a\) 和 \(b\) 被 \(m\) 除后所得的最小非负余数相等，即若 \[ \begin{aligned} a=q_1m+r_1&,0\leq r_1<m\\ b=q_2m+r_2&,0\leq r_2<m, \end{aligned} \] 则 \(r_1=r_2\)。

性质Ⅰ\(\quad\) 同余是一种等价关系，即有 \[ \begin{aligned} a\equiv a\pmod{m}\\ a\equiv b\pmod{m}\iff b\equiv a\pmod{m}\\ a\equiv b\pmod{m}\;,\;b\equiv c\pmod{m}\Rightarrow a\equiv c\pmod{m} \end{aligned} \] 性质Ⅱ\(\quad\) 同余式可以相加，即若有 \[ a\equiv b\pmod{m}\;,\;c\equiv d\pmod{m}\tag{2} \]

则有

\[ a+c\equiv b+d\pmod m \]

性质Ⅲ\(\quad\) 同余式可以相乘，即若式 \((2)\) 成立，则

\[ ac\equiv bd\pmod m \]

性质Ⅳ\(\quad\) 设 \(f(x)=a_nx^n+\cdots+a_0\)，\(g(x)=b_nx^n+\cdots+b_0\) 是两个整系数多项式，满足

\[ a_j\equiv b_j\pmod m\;,\;0\leq j<n\tag{3} \]

那么，若 \(a\equiv b\pmod m\)，则

\[ f(a)\equiv g(b)\pmod m \]

特别地，对所有整数 \(x\) 有

\[ f(x)\equiv g(x)\pmod m\tag{4} \]

定义2\(\quad\) 设 \(f(x)=a_nx^n+\cdots+a_0\) 和 \(g(x)=b_nx^n+\cdots+b_0\) 是两个整系数多项式。当满足条件 \((3)\) 时，称多项式 \(f(x)\) 同余于多项式 \(g(x)\) 模 \(m\)，记作

\[ f(x)\equiv g(x)\pmod m \]

当满足 \(f(x)\equiv g(x)\pmod m\) 时，称多项式 \(f(x)\) 等价于多项式 \(g(x)\) 模 \(m\)，式 \((4)\)称为模 \(m\) 的恒等同余式

性质Ⅴ\(\quad\) 设 \(d\geq1\)，\(d\mid m\)，那么，若式 \((1)\) 成立，则 \(a\equiv b\pmod d\)

性质Ⅵ\(\quad\) 设 \(d\not=0\)，那么 \(a\equiv b\pmod m\) 等价于 \(da\equiv db\pmod{\left\vert d\right\vert m}\)

性质Ⅶ\(\quad\) 同余式 \(ca\equiv cb\pmod m\) 等价于 \(a\equiv b\pmod{\frac m{\gcd(c,m)}}\)

特别地，当 \(\gcd(c,m)=1\) 时，上述同余式等价于 \(a\equiv b\pmod m\)

性质Ⅷ\(\qquad\) 若 \(m\geq1\)，\(\gcd(a,m)=1\)，则存在 \(c\) 使得

\[ ca\equiv1\pmod m\tag{5} \]

定义3\(\quad\) 若存在 \(m\geq1\)，\(\gcd(a,m)=1\)，且满足式 \((5)\)，我们把 \(c\) 称为 \(a\) 对模 \(m\) 的逆，记作 \(a^{-1}\pmod m\) 或 \(a^{-1}\)

性质Ⅸ\(\quad\) 同余式组

\[ a\equiv b\pmod{m_j}\;,\;j=1,2,\cdots,k \]

同时成立的充要条件是

\[ a\equiv b\pmod{[m_1,m_2,\cdots,m_k]} \]

1.2\(\quad\)同余类与剩余系

定义4（同余类和剩余系）\(\quad\) 对于 \(\forall a\in [0,m-1]\)，集合 \(\{a+km\}(k\in\mathbb{Z})\) 的所有数模 \(m\) 同余，余数都是 \(a\)，该集合成为模 \(m\) 的同余类，简记为 \(\overline{a}\)。

模 \(m\) 的同余类一共有 \(m\) 个，分别为 \(\overline{0},\overline{1},\overline{2},\cdots,\overline{m-1}\)。它们构成 \(m\) 的完全剩余系。

\(1\sim m\) 中与 \(m\) 互质的数代表的同余类共有 \(\phi(m)\) 个，它们构成 \(m\) 的简化剩余系。

二、费马小定理和欧拉定理

前置芝士：欧拉函数。

利用同余基本知识和欧拉函数，即可证明费马小定理和欧拉定理。

2.1\(\quad\)费马小定理

定理2（费马小定理）\(\quad\) 若 \(p\) 是质数，则对于任意整数 \(a\)，有

\[ a^p\equiv a\pmod p \]

2.2\(\quad\)欧拉定理

定理3（欧拉定理）\(\quad\) 若正整数 \(a,n\) 互质，则

\[ a^{\phi(n)}\equiv1\pmod n \]

其中，\(\phi(n)\) 为欧拉函数。

特别地，当 \(p\) 是质数时，\(\phi(p)=p-1\)，并且只有 \(p\) 的倍数与 \(p\) 不互质，所以，只要 \(a\) 不是 \(p\) 的倍数，就有

\[ a^{p-1}\equiv1\pmod p \]

两边同乘 \(a\) 就是费马小定理。

证\(\quad\) 设 \(n\) 的简化剩余系为 \(\{\overline{a_1},\overline{a_2},\cdots,\overline{a_{\phi(n)}}\}\)。对于 \(\forall a_i,a_j\)，若 \(a\times a_i\equiv a\times a_j\pmod n\)，则 \(a\times(a_i-a_j)\equiv 0\)。因为 \(a,n\) 互质，所以 \(a_i-a_j\equiv 0\)，即 \(a_i\equiv a_j\)。故当 \(a_i\not=a_j\) 时，\(aa_1,aa_j\) 也代表不同的同余类。

又因为简化剩余系关于模 \(n\) 乘法封闭，故 \(\overline{aa_1}\) 也在简化剩余系集合中。因此，集合 \(\{\overline{a_1},\overline{a_2},\cdots,\overline{a_{\phi(n)}}\}\) 与集合 \(\{\overline{aa_1},\overline{aa_2},\cdots,\overline{aa_{\phi(n)}}\}\) 都能表示 \(n\) 的简化剩余系，故有

\[ a^{\phi(n)}\prod\limits_{i=1}^{\phi(n)} a_i\equiv\prod\limits_{i=1}^{\phi(n)}aa_i\equiv \prod\limits_{i=1}^{\phi(n)}a_i\pmod n \]

两边同时除以 \(\prod\limits_{i=1}^{\phi(n)}a_i\) 可得

\[ a^{\phi(n)}\equiv1\pmod n \]

当 \(p\) 为质数时，\(\phi(p)=p-1\)，并且只有 \(p\) 的倍数与 \(p\) 不互质。所以，只要 \(a\) 不是 \(p\) 的倍数，\(a^{p-1}\equiv1\pmod p\) 显然成立。两边同乘 \(a\) 即费马小定理。

证毕。

2.3\(\quad\)欧拉定理的推论

推论1（欧拉定理推论）\(\quad\) 若正整数 \(a,n\) 互质，则对于任意正整数 \(b\)，有

\[a^b\equiv a^{b\mod{\phi(n)}}\pmod n\]

证\(\quad\) 设 \(b=q\times\phi(n)+r\)，其中 \(0\leq r<\phi(n)\)，即 \(r=b\mod{\phi(n)}\)。利用欧拉定理有

\[ a^b\equiv a^{q\times\phi(n)+r}\equiv(a^{\phi(n)})^q\times a^r\equiv 1^q\times a^r\equiv a^r\equiv a^{b\mod{\phi(n)}+\phi(n)}\pmod n \]

证毕。

特别地，当 \(a,n\) 不一定互质且 \(b>\phi(n)\) 时，有

\[ a^b\equiv a^{b\mod{\phi(n)+\phi(n)}}\pmod n \]

2.4\(\quad\)光速幂

给定 \(a\) 和 \(c\)，每次询问给出 \(b\)，求 \(a^b\bmod c\)。

我们可以先运用 \(a^b\bmod a^{b\bmod \phi(n)+\phi(n)}\pmod c\)，将 \(b\) 缩小到 \(2\phi(c)(<2c)\) 的范围，有

\[ a^b=(a^{\sqrt c})^{\left\lfloor\frac{b}{\sqrt c}\right\rfloor}\times a^{b\bmod \sqrt c} \]

其中，\(\frac{b}{\sqrt c}<2\sqrt c\)，\(b\bmod \sqrt c<\sqrt c\)

我们预处理 \((a^{\sqrt c})^i\) 和 \(a^j\) 即可 \(O(\sqrt c)\) 预处理，\(O(1)\) 回答询问。

三、扩展欧几里得算法

前置芝士：欧几里得算法。

本部分着重介绍扩展欧几里得算法、裴蜀定理和乘法逆元相关知识。

3.1\(\quad\)裴蜀定理

定理4（裴蜀定理） \(\quad\) \(\forall a,b\in\mathbb{Z}\)，一定存在一组 \(x,y\in\mathbb{Z}\)，满足

\[ ax+by=\gcd(a,b) \]

证\(\qquad\) 在欧几里得算法的最后一步，即 \(b=0\) 时，我们一定会得出一组整数 \(\begin{cases}x=1\\b=0\end{cases}\)，使得 \(a\times1+0\times0=\gcd(a,0)\)。

由欧几里得算法得 \(\gcd(a,b)=\gcd(b,a\bmod b)\)。假设存在一组整数 \(x,y\)，满足 \(bx+(a\bmod b)y=\gcd(b,a\bmod b)\)。

因为 \(bx+(a\bmod b)y\)

\(\begin{aligned} \;\;&=bx+(a-b\left\lfloor\dfrac{a}{b}\right\rfloor)y \\ &=bx+ay-b\left\lfloor\dfrac{a}{b}\right\rfloor y \\ &=ay+b(x-b\left\lfloor\dfrac{a}{b}\right\rfloor) \end{aligned}\)

所以，令 \(x'=y\)，\(y'=x-\left\lfloor\dfrac{a}{b}\right\rfloor y\)，就得到了 \(ax'+by'=\gcd(a,b)\)。

对以上过程应用数学归纳法，可知裴蜀定理一定成立。

证毕。

3.2\(\quad\)扩展欧几里得算法

上面证明的过程中，我们通过 \(ax+(a\bmod b)y=\gcd(a,b)\) 推出了 \(ax'+by'=\gcd(a,b)\)。按照欧几里得算法的思路，并给出整数 \(x\) 和整数 \(y\) 的计算方法成为扩展欧几里得算法。

下面给出扩展欧几里得算法过程：

1. 给定 \(a\) 和 \(b\)，递归 \(\operatorname{exgcd}(a,b)\)；

2. 是否 \(b=0\)。如果是，返回 \(\begin{cases}x=1\\y=0\end{cases}\)；如果不是，递归 \(\operatorname{exgcd}(b,a\bmod b)\)，并重复进行1和2操作，直至条件成立；

3. 每次递归结束后，计算 \(\begin{cases}x'=y\\y'=x-\left\lfloor\dfrac{a}{b}\right\rfloor y\end{cases}\)。

也可以在算法过程中顺便记录 \(\gcd(a,b)\)。

ll exgcd(ll a,ll b,ll &x,ll&y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    ll d=exgcd(b,a%b,x,y);
    ll temp=x;
    x=y;
    y=temp-a/b*y;
    return d;
}

ll a,b,x,y;
cin>>a>>b;
ll d=exgcd(a,b,x,y);

上述程序求出方程 \(ax+by=\gcd(a,b)\) 的一组特解 \(x_0,y_0\)，并返回 \(\gcd(a,b)\)，即 \(d\)。

对于方程 \(ax+by=c\)，当且仅当 \(d\mid c\) 时有解。我们可以求出 \(ax+by=d\) 的一组特解 \(x_0,y_0\)，然后令 \(x_0,y_0\) 同时乘上 \(\dfrac{c}{d}\)，就得到了方程 \(ax+b=c\) 的特解

\[ \dfrac{c}{d}x_0\;,\;\dfrac{c}{d}y_0 \]

对于方程 \(ax+by=d\)，我们将其特解表示为 \(x_0,y_0\)，有 \(a(x+m)+b(y-n)=ax+by+am-bn=d\)。因为 \(ax+by=d\)，可以推出 \(am-bn=0\Rightarrow am=bn\Rightarrow \dfrac{a}{b}=\dfrac{n}{m}\)。由于 \(\gcd(a,b)=d\)，故 \(m\) 和 \(n\) 最小只能取 \(\dfrac{b}{d}\) 和 \(\dfrac{a}{d}\)，能保证 \(m\) 和 \(n\) 为整数。所以，方程 \(ax+by=d\) 的通解为

\[ \begin{cases}x_1=x_0+\dfrac{b}{d}k\\ \\y_1=y_0-\dfrac{a}{d}k\end{cases}(k\in\mathbb{Z}) \]

3.3\(\quad\)线性同余方程

给定整数 \(a,b,m\)，求一个整数 \(x\) 满足 \(ax\equiv b\pmod m\)，或者给出无解。

定义5（线性同余方程）\(\qquad\) 在整数域内，关于 \(x\) 的同余方程 \(ax\equiv b\pmod m\) 称为一次同余方程，也称线性同余方程。

\(ax\equiv b\pmod m\) 等价于 \(m\mid (ax-b)\)，一定存在一个整数 \(k\)，有 \(ax+mk=b\)。我们可以利用扩展欧几里得算法对其进行计算。

3.4\(\quad\)乘法逆元

定义6（乘法逆元）\(\qquad\) 若整数 \(b,m\) 互质，并且 \(b\mid a\)，则存在一个整数 \(x\)，使得 \(\dfrac{a}{b}\equiv ax\pmod m\)。称 \(x\) 为 \(b\) 的模 \(m\) 乘法逆元，记为 \(b^{-1}\pmod m\)。

因为 \(\dfrac{a}{b}\equiv a\times b^{-1}\equiv\dfrac{a}{b}\times b\times b^{-1}\pmod m\)，所以 \(b\times b^{-1}\equiv1\pmod m\)。

下面是一些求解乘法逆元的方法。

方法一：解线性同余方程求解乘法逆元

如果只保证 \(b,m\) 互质，那么乘法逆元可以通过求解同余方程 \(bx\equiv1\pmod m\) 得到。算法过程已在上文中提及，不再赘述。

方法二：快速幂求解乘法逆元

本方法使用有前提条件。

如果 \(m\) 是质数，并用 \(p\) 表示 \(m\)，并且 \(b<p\)，根据费马小定理， \(b^{p-1}\equiv1\pmod p\)，即

\[ b\times b^{p-2}\equiv1\pmod p \]

因此，当模数 \(p\) 为质数时，\(b^{p-2}\) 即为 \(b\) 的乘法逆元。

我们直接对 \(b^{p-2}\) 进行快速幂计算即可得到答案。

方法三：线性求解乘法逆元

给定 \(n,p\)，求出 \(1,2,\cdots,n\) 在模 \(p\) 意义下的乘法逆元。

显而易见，\(1^{-1}\equiv1\pmod p\)。

假设当我们递归到 \(i(i>1)\) 时已经把前 \(i-1\) 个的乘法逆元算出来了，我们设 \(j=p\bmod i\)，\(k=\left\lfloor\dfrac{p}{i}\right\rfloor\)，有 \(p=ki+j\)，即

\[ ki+j\equiv 0\pmod p \]

两边同乘 \(i^{-1}j^{-1}\) 得

\[ \begin{aligned} kj^{-1}+i^{-1}&\equiv0\pmod p\\ i^{-1}&\equiv kj^{-1}\pmod p\\ i^{-1}&\equiv \left\lfloor\dfrac{p}{i}\right\rfloor(p\bmod i)^{-1}\pmod p \end{aligned} \]

void work(){
    scanf("%d%d",&n,&p);
    inv[1]=1;
    for(int i=2;i<=n;i++){
        inv[i]=(long long)(p - p / i) * inv[p % i] % p;
    }
    for(int i=1;i<=n;i++) printf("%d\n",inv[i]);
}

方法四：线性求解任意 \(n\) 个数的逆元

任意给定 \(n\) 个数 \(a_1,a_2,\cdots,a_n\)，求它们在模 \(p\) 意义下的乘法逆元，其中，\(p\) 为质数。

我们设

\[ s_i=\prod_{i=1}^ia_i \]

通过快速幂或者扩展欧几里得算法求得 \(s_i\) 的乘法逆元记为 \(sv_i\)，即

\[ sv_i=s_i^{-1}\pmod p \]

我们将 \(sv_1\) 乘上 \(a_i\)，会与 \(a_i^{-1}\pmod p\) 相消，得

\[ a_i\times sv_1=sv_{i-1} \]

我们就能递推线性求解乘法逆元。

ll n,p,k,a[MAXN],s[MAXN],t[MAXN];
ll ans=0,temp;
int qpow(int a,int b,int mod){
    int ans=1;
    for(;b;b>>=1){
        if(b&1) ans=(long long)ans*a%mod;
        a=(long long)a*a%mod;
    }
    return ans;
}
void work(){
    s[0]=1;
    t[n+1]=1;
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]*a[i]%p;
    }
    t[n+1]=qpow(s[n],p-2,p);
    for(int i=n;i;i--){
        t[i]=t[i+1]*a[i]%p;
    }
    temp=k;
    for(int i=1;i<=n;i++){
        ans=(ans+(t[i+1]*s[i-1]%p)*temp)%p;
        temp=temp*k%p;
    }
    printf("%lld",ans);
}

3.5\(\quad\)威尔逊定理

定理5（威尔逊定理）\(\quad\) 对于任意素数 \(p\)，有 \((p-1)!\equiv-1\pmod p\)。

证\(\quad\) 我们知道，\(x^2\equiv1\pmod p\) 的解只有 \(x\equiv\pm1\pmod p\)，所以 \(2\sim p-2\) 和逆元两两对应。剩下 \(1\times (p-1)\equiv -1\pmod p\)。

证毕。

四、中国剩余定理

前置芝士：乘法逆元。

本节主要介绍有关中国剩余定理和扩展中国剩余定理，是解决线性同余方程组问题的重要方法。

4.1\(\quad\)中国剩余定理

定理6（中国剩余定理，孙子定理）\(\quad\) 设 \(m_1,m_2,\cdots,m_n\) 是两两互质的整数，\(m=\prod_{i=1}^n{m_i}\)，\(M_i=m/m_i\)，\(t_i\) 是线性同余方程 \(M_it_i\equiv1\pmod{m_i}\) 的一个解。对于任意的 \(n\)个整数 \(a_1,a_2,\cdots,a_n\)，方程组

\[ \begin{cases}x\equiv a_1\pmod{m_1}\\ x\equiv a_2\pmod{m_2}\\ \cdots\\ x\equiv a_n\pmod{m_n}\end{cases} \]

有整数解，解为 \(x=\sum_{i=1}^na_iM_it_i\)。

证\(\quad\) 因为 \(M_i=m/m_i\) 是除 \(m_i\) 之外所有模数的倍数，所以 \(\forall k\not=i\;,\;a_iM_it_i\equiv0\pmod{m_k}\)。又因为 \(a_iM_it_i\equiv a_i\pmod{m_i}\)，所以代入 \(x=\sum_{i=1}^na_iM_it_i\)，原方程组成立。

证毕。

按照中国剩余定理，我们可以计算线性同余方程组的一个通解（最小解）。另外，我们可以用扩展欧几里得算法求解逆元。

int n,a[MAXN],m[MAXN];
ll M,ans,summ[MAXN];
ll qpow(int a,int b,int mod){
    ll w=1;
    for(;b;b>>=1){
        if(b&1) w=w*a%mod;
        a=a*a%mod;
    }
    return w;
}
void exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1,y=0;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
void work(){
    M=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>m[i]>>a[i];
        M*=m[i];
    }
    for(int i=1;i<=n;i++) summ[i]=M/m[i];
    for(int i=1;i<=n;i++){
        ll x=0,y=0;
        exgcd(summ[i],m[i],x,y);
        if(x<0) x+=m[i];
        ans+=a[i]*summ[i]*x;
        ans%=M;
    }
    cout<<ans;
}

4.2\(\quad\)扩展中国剩余定理

中国剩余定理只能处理模数两两互质的情况，无法处理普遍情况。我们可以使用扩展中国剩余定理进行推算。

对于每两个线性同余方程组 \(x\equiv a_1\pmod {m_1}\;,\;x\equiv a_2\pmod{m_2}\)，将其转化为不定方程 \(x=pm_1+a_1=qm_2+a_2\)，移项有

\[ pm_1-qm_2=a_2-a_1 \]

有裴蜀定理得，方程组有整数解当且仅当 \(\gcd(m_1,m_2)|(a_2-a_1)\)。这时我们就可以用扩展欧几里得算法得到一组可行解 \((p,q)\)，则原来的两个方程可以合并为

\[ x\equiv m_1p+a_1\pmod{\text{lcm}(m_1,m_2)} \]

我们逐一进行合并即可求解。

typedef __int128 ll;
int n;
struct node{
    ll a,m;
};
queue<node> qu;
ll exgcd(ll a,ll b,ll &x,ll&y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    ll d=exgcd(b,a%b,x,y);
    ll temp=x;
    x=y;
    y=temp-a/b*y;
    return d;
}
ll lcm(ll x,ll y,ll d){
    return x/d*y;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        long long a,b;
        scanf("%lld%lld",&a,&b);
        qu.push(node{b,a});
    }
    for(int i=1;i<n;i++){
        node a,b;
        a=qu.front();qu.pop();
        b=qu.front();qu.pop();
        ll k1,k2;
        if(a.a>b.a) swap(a,b);
        ll c=b.a-a.a;
        ll d=exgcd(a.m,b.m,k1,k2);
        k1*=c/d;
        k2*=c/d;
        ll q=b.m/d,p=a.m/d;
        if(k1<0){
            ll k=ceil((1.0-k1)/q);
            k1+=k*q;
            k2-=k*p;
        }
        else{
            ll k=(k1-1)/q;
            k1-=k*q;
            k2+=k*p;
        }
        node now;
        now.a=k1*a.m+a.a;
        now.m=q*a.m;
        now.a%=now.m;
        qu.push(now);
    }
    node ans=qu.front();
    printf("%lld",(long long)(ans.a%ans.m));
    return 0;
}

五、高次同余方程与BSGS算法

5.1\(\quad\)BSGS算法

给定 \(a,b,p\)，已知 \(a\perp p\)，求解 \(x\) 满足

\[ a^x\equiv b\pmod p \]

令 \(x=A\left\lceil\sqrt p\right\rceil-B\)，其中， \(0\leq A,B\leq \left\lceil\sqrt p\right\rceil\)，有 \(a^{A\left\lceil\sqrt p\right\rceil-B}\equiv b\pmod p\)，整理得

\[ a^{A\left\lceil\sqrt p\right\rceil}\equiv ba^B\pmod p \]

我们逐一枚举 \(B\) 即可知道所有 \(ba^B\)。然后建立 hash 表，逐一计算 \(a^{A\left\lceil\sqrt p\right\rceil}\)，找到与之相等的 \(ba^B\) 即可求出 \(x=A\left\lceil\sqrt p\right\rceil-B\)。

时间复杂度 \(O(\sqrt p)\)。

ll BSGS(){
    map<ll,ll> hash;
    hash.clear();
    b%=p;
    ll t=sqrt(p)+1;
    for(ll i=0;i<t;i++){
        ll val=b*qpow(a,i,p)%p;
        hash[val]=i;
    }
    a=qpow(a,t,p);
    if(a==0) return (b==0?1:-1);
    for(ll i=0;i<=t;i++){
        ll val=qpow(a,i,p);
        ll j=hash.find(val)==hash.end()?-1:hash[val];
        if(j>=0&&i*t-j>=0) return i*t-j;
    }
    return -1;
}