写在前面

在某次集训比赛时遇到了$esBSGS$毒瘤题，被大佬们暴捶，过了一个多月本蒟蒻才开始学习$BSGS\text{&}exBSGS$

BSGS

$BabyStepGiantStep$算法，即大步小步算法，缩写为$BSGS$，而$esBSGS$，顾名思义，就是$BSGS$的拓展。

$BSGS$用来解决如下问题：

给定一个质数$P(2\leq P < 2^{31})$，以及一个整数$Y(2\leq A < P)$，一个整数$Z(2\leq Z <P)$，求最小的$X$，满足$Y^X \equiv Z \mod P$

例题：Luogu P3846 [TJOI2007]可爱的质数

算法思路如下：

设$m=\sqrt{P}$，$X=a\times m-b$，$a\in [0,m+1]$，$n \in [0,m)$。

那么$Y^{a \times m-b}\equiv Z \mod P$

$Y^{a\times m}\equiv Z \times Y^{b} \mod P$，

所以只要$O(m)$记录一下右边的值，然后枚举左边，查表即可。

#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;

#define re register
#define int long long 

class Quick_Input_Output{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Rd)+fread(Rd,1,S,stdin),A==B)?EOF:*A++)
        char Rd[S],*A,*B;
        #define pc putchar
    public:
        #undef gc
        #define gc getchar 
        inline int read(){
            int res=0,f=1;char ch=gc();
            while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc();}
            while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=gc();
            return res*f;
        }
        inline void write(int x){
            if(x<0) pc('-'),x=-x;
            if(x<10) pc(x+'0');
            else write(x/10),pc(x%10+'0');
        }
        #undef gc
        #undef pc
}I;
#define File freopen("%name%.in","r",stdin);freopen("%name%.out","w",stdout);

int p,y,z,m,ans;
map<int,int> mp;
int fpow(int a,int b){
    int s=1;
    while(b){
        if(b&1) s*=a,s%=p;
        a*=a;
        a%=p;
        b>>=1;
    }
    return s;
}
int calc(int x){
    int s=z;
    s*=fpow(y,x);s%=p;
    return s; 
}
signed main(){
//  File
    p=I.read();y=I.read();z=I.read();
    if(y==1) return puts("0"),0;
    m=sqrt(p)+1;
    mp.clear();
    for(int pw=z,i=0;i<m;i++){
        mp[pw]=i;
        pw*=y;pw%=p;
    }
    ans=-1;
    for(int s=1,pw=fpow(y,m),i=1;i<=m+1;i++){
        s*=pw;s%=p;
        if(mp.count(s)){
            ans=i*m-mp[s];
            break;
        }
    }
    if(ans==-1) return puts("no solution"),0;
    I.write(ans);putchar('\n');
    return 0;
}

exBSGS

$exBSGS$顾名思义（大雾），就是$BSGS$的拓展。适用于解决如下问题：

给定一个整数$P(2\leq P < 2^{31})$，以及一个整数$Y(2\leq A < P)$，一个整数$Z(2\leq Z <P)$，求最小的$X$，满足$Y^X \equiv Z \mod P$

例题：Luogu P4195 【模板】exBSGS/Spoj3105 Mod

算法思路如下：

对于$gcd(y, p)\ne1$怎么办？

我们把它写成$y\times y^{x-1}+k\times p=z, k\in Z$的形式

根据$exgcd$的理论
那么如果$gcd(y,p)$不是$z$的约数就不会有解

设$d=gcd(y,p)$
那么$\frac{y}{d}\times y^{x-1}+k\times \frac{p}{d}=\frac{z}{d}$

递归到$d=1$
设之间的所有的$d$乘积为$g$，递归$c$次
令$x’=x-c, p’=\frac{p}{g},z’=\frac{z}{g}$
那么$y^{x’}\times \frac{y^c}{g}=z'(mod \ p’)$

那么$BSGS$求解就好了

#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<unordered_map>
using namespace std;

#define re register
#define int long long 

class Quick_Input_Output{
    private:
        static const int S=1<<21;
        #define tc() (A==B&&(B=(A=Rd)+fread(Rd,1,S,stdin),A==B)?EOF:*A++)
        char Rd[S],*A,*B;
        #define pc putchar
    public:
        #undef gc
        #define gc getchar 
        inline int read(){
            int res=0,f=1;char ch=gc();
            while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc();}
            while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=gc();
            return res*f;
        }
        inline void write(int x){
            if(x<0) pc('-'),x=-x;
            if(x<10) pc(x+'0');
            else write(x/10),pc(x%10+'0');
        }
        #undef gc
        #undef pc
}I;
#define File freopen("%name%.in","r",stdin);freopen("%name%.out","w",stdout);
int p,y,z,m,ans;
std::unordered_map<int,int> Hash;
int fpow(int a,int b){
    int s=1;a%=p;
    while(b){
        if(b&1) s*=a,s%=p;
        a*=a;
        a%=p;
        b>>=1;
    }
    return s;
}
int gcd(int a,int b){
    return !b?a:gcd(b,a%b);
}
int EX_BSGS(){
    y%=p;z%=p;
    if(y==1) return puts("0"),0;
    Hash.clear(); 
    re int cnt=0,t=1; 
    for(int d=gcd(y,p);d!=1;d=gcd(y,p)){
        if(z%d) return puts("No Solution"),0;
        ++cnt,z/=d,p/=d,t=1ll*t*y/d%p;
        if(z==t) return I.write(cnt),putchar('\n'),0;
    }
    m=sqrt(p)+1;
    for(int pw=z,i=0;i<m;i++){
        Hash[pw]=i;
        pw*=y;pw%=p;
    }
    ans=-1;
    for(int s=t,pw=fpow(y,m),i=1;i<=m;i++){
        s*=pw;s%=p;
        if(Hash.find(s)!=Hash.end()){
            ans=i*m-Hash[s]+cnt;
            break;
        }
    }
    if(ans==-1) return puts("No Solution"),0;
    I.write(ans);putchar('\n');
}
signed main(){
//  File
    while(1){
        y=I.read();p=I.read();z=I.read();
        if(p==0&&y==0&&z==0) return 0;
        EX_BSGS();
    }
    return 0;
}