题解 P4195 【【模板】扩展 BSGS/exBSGS】

我的 BSGS 算法学习笔记

P4195 【模板】扩展 BSGS/exBSGS

SP3105 MOD - Power Modulo Inverted

好耶，紫色的双倍经验！

普通的 BSGS 只能解决 a 与 p 互质的情况，而 exBSGS 不需要这个条件。

不互质咋办？变成互质！

OI Wiki 上的讲解

方程两边同时除以 \gcd(a,p) ，注意模数 p 也要除，若 \gcd(a,p) \nmid b 则无解。

若仍不互质则重复进行上述过程，直至 p 与 a 互质。

记 d 为每次的 \gcd 的乘积，一共除了 cnt 次，则方程转化为：

因为 a\perp \frac{p}{d} ，所以 \frac{a^{cnt}}{d} 在 \bmod \frac{p}{d} 意义下有逆元，移项求解 x-cnt 然后加上 cnt 即可。

当然有时候 x=cnt ，这种情况直接返回 cnt 就好了。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>

using namespace std;

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

map <int,int> _hash;
inline int exBSGS(int a,int b,int p)
{
    a%=p; b%=p;
    if(b == 1 || p == 1) return 0;
    int d,ax=1,cnt=0,x,y;
    while((d=exgcd(a,p,x,y))^1)
    {
        if(b%d) return -1;
        b/=d; p/=d; cnt++;
        ax=1ll*ax*(a/d)%p;
        if(ax == b) return cnt;
    }

    exgcd(ax,p,x,y);
    int inv=(x%p+p)%p;
    b=1ll*b*inv%p;

//  BSGS
    _hash.clear();
    int t=ceil(sqrt(p)),val=1;
    for(int i=0;i<t;i++)
    {
        _hash[1ll*b*val%p]=i;
        val=1ll*val*a%p;
    }
    a=val; val=1;

    if(!a) return !b? 1+cnt:-1;
    for(int i=0,j;i<=t;i++)
    {
        j=_hash.find(val) == _hash.end()? -1:_hash[val];
        if(~j && i*t-j >= 0) return i*t-j+cnt;
        val=1ll*val*a%p;
    }
    return -1;
}

int main()
{
//  freopen("work.in","r",stdin); freopen("work.out","w",stdout);
    int a,b,p,ans;
    while(scanf("%d%d%d",&a,&p,&b) == 3 && a && b && p)
    {
        ans=exBSGS(a,b,p);
        if(~ans) printf("%d\n",ans);
        else puts("No Solution");
    }
//  fclose(stdin); fclose(stdout);
    return 0;
}

由于我太菜，在 luogu 上没找到其他 exBSGS 的题，如果您有这样的题目推荐，可以私信或者下方回复。谢谢您的鼓励和支持！

\text{Thank you for your reading !}