BSGS是Baby-step-Giant-step的简写，是用来求解一类问题的算法
模型：求解方程$A^{x}equiv B$ mod $C$，保证C为质数
首先，我们分析一下暴力的方法：直接从0开始枚举x计算，直到求出答案为止
时间复杂度？
$O(C)$
等等，为什么是$O(C)$?
根据费马小定理，$A^{C-1}equiv 1$mod $C$，因此仅需枚举$xin [0,C-1]$即可找出所有可能的结果，比较即可
这个复杂度不够优秀，有没有什么方法能降下来？
分块！
设$m=sqrt{C}$，那么每一个$x$都可以写成$x=i*m+j$的形式，由于有$x<C$，因此$iin [0,m],jin [0,m]$！
优化在哪了？
我们发现，如果把$x$变成这个形式，那么我们就可以对原表达式进行变形：
$A^{x}equiv B$ mod $C$
$A^{i*m+j}equiv B$ mod $C$
$A^{i*m}*A^{j}equiv B$ mod $C$
乱七八糟鼓捣了半天，这是要干啥？
我们发现，$A^{i*m}$这一项的取值不超过$sqrt{C}$个，因此我们可以将之预处理出来，同时$A^{j}$的取值也不超过$sqrt{C}$个，同样可以预处理，而且我们发现，如果将$A^{i*m}$这一项作为已知的系数进行枚举，那么这就变成了一个同余方程，用ex_gcd或费马小定理求解是可以在$O(log2C)$（大概是这个复杂度）的时间内求出对应的$A^{j}$的！
于是我们仅需检验这一$A^{j}$是否出现过即可，借助map或hash表，这一过程可以被简化成$O(log)$或$O(1)$的！
于是总复杂度即为$O(sqrt{C}log2(C))$
贴代码
（这个是bzoj 2242的代码，这是一道板子题，前20分是快速幂，中间35分是ex_gcd或者费马小定理，最后45分是BSGS）
#include <cstdio> #include <cmath> #include <map> #define ll long long using namespace std; ll y,z,p; ll mul[200005]; map <ll,int> M; int T,k; ll gcd(ll a,ll b) { return b?gcd(b,a%b):a; } ll pow_mul(ll a,ll b,ll mod) { ll ret=1; while(b) { if(b&1)ret=ret*a%mod; a=a*a%mod,b>>=1; } return ret; } int main() { scanf("%d%d",&T,&k); while(T--) { scanf("%lld%lld%lld",&y,&z,&p); if(k==1)printf("%lld ",pow_mul(y,z,p)); else if(k==2) { if(gcd(y,p)!=1)printf("Orz, I cannot find x! "); else printf("%lld ",pow_mul(y,p-2,p)*z%p); }else { M.clear(); if(z==1){printf("0 ");continue;} ll tt=(ll)sqrt(p)+1; ll ed=0; for(ll i=0;i*tt<=p;i++)mul[i+1]=pow_mul(y,i*tt,p),ed=i; for(ll i=0;i<=tt;i++)M[pow_mul(y,i,p)]=i+1; bool flag=0; for(ll i=0;i<=ed;i++) { if(gcd(mul[i+1],p)!=1)continue; ll temp=pow_mul(mul[i+1],p-2,p)*z%p; if(M[temp]){printf("%lld ",M[temp]-1+i*tt);flag=1;break;} } if(!flag)printf("Orz, I cannot find x! "); } } return 0; }