BSGS

又称北上广深或拔山盖世

运用了分块思想

至于i，j的范围，还是要说一下

i是1到sqrt的左闭右闭，因为是枚举一块一块的（大步），所以显然

j是0到sqrt的左闭右开，因为零散的可有可无，而如果可以取到sqrt的话，为什么不并入i中呢？

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
LL read()
{
    LL f=1,x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x*f;
}
map<LL,LL>ma;
LL p; 
LL quick_pow(LL a,LL x)
{
    LL ans=1;
    while(x)
    {
        if(x&1) ans=ans*a%p;
        a=a*a%p;
        x=x/2;
    }
    return ans%p;
}
int main()
{
    p=read();LL Y=read(),Z=read();
    ma.clear();
    if(Y==1)
    {
        printf("0
");
        return 0;
    } 
    int ans=-1,m=sqrt(p)+1;
    int tmp=Z;
    for(int i=0;i<m;++i)//小步 
    {
        ma[tmp]=i;
        tmp=1LL*tmp*Y%p;
    }
    int t=quick_pow(Y,m);
    tmp=1;
    for(int i=1;i<=m;++i)//大步 
    {
        tmp=1LL*tmp*t%p; 
        if(ma.count(tmp))
        {
            printf("%lld
",i*m-ma[tmp]);
            return 0;
        }
    }
    printf("no solution");
}

---

扩展BSGS

模数不为质数的情况

那我们就可以一直同除gcd，直到A，C互质

具体看代码

//a=b(mod p) ---> a/c=b/c(mod p/c)
void exbsgs(LL A,LL B,LL C)
{
    ma.clear();
    if(B==1){printf("0
"); return;}
    int k=0;LL tmp=1;
    while(1)
    {
        LL d=gcd(A,C);
        if(d==1)break;
        if(B%d) printf("Math Error
");return;
        B/=d;C/=d;
        tmp=tmp*(A/d)%C;//注意A不要像B，C那样除d，因为求的是A^x 
        k++;
        if(tmp==B){printf("%d
",k);return;}//因为小于了k的判不到，在这里判 
    }
    LL m=sqrt(C)+1;
    tmp=B;
    for(int i=0;i<m;++i)
    {
        ma[tmp]=i;
        tmp=tmp*A%C;
    }
    LL t=quick(A,m,C);
    tmp=1;
    for(int i=1;i<=m;++i)
    {
        tmp=tmp*t%C;
        if(ma.count(tmp))
        {printf("%lld
",i*m-ma[tmp]+k);return;    } //记得加上k 
    }
    printf("Math Error
");return;
}