BSGS算法，即大小步算法（Baby-Step-Giant-Step）
俗称北上广深、拔山盖世算法。
用途
可以在$O(sqrt{P})$的时间负复杂度求出形如$A^xequiv B ( mod P ),(Gcd(P,A)=1)$的方程的最小非负整数解。
实现
根据费马小定理，我们不难证明若最小非负整数$x$存在，那么一定有$x<P$，那么我们不妨假设$x=kn-m,A^{kn-m}equiv B$，其中$n$为$sqrt{P}$向上取整，$k、m$为不超过$n$的正整数。
这样做有什么好处呢？我们发现$k、m$都是取值范围小于$sqrt{P}$的正整数，我们想要利用好这条性质，就要把式子变一下形:
$$ A^{kn-m}equiv B ( mod P )$$
$$ A^{kn}equiv A^{m}cdot B ( mod P )$$
我们令$G=A^n( mod P )$，则
$$ G^kequiv A^{m}cdot B ( mod P )$$
这样，我们就可以先处理处每一个$ A^{m}cdot B $，存进哈希表中，再求出$G=A^n$，并依次枚举$ G^k $在哈希表中是否存在，优先取$k$小的即可，最终就有$x=kn-m$。
扩展
不难看出，以上过程依托费马小定理限定了$x$的取值范围，所以限制是$(Gcd(P,A)=1)$，但如果不是这样呢？
我们不妨假设$(Gcd(P,A)=d),A=a imes d，B=b imes d，P=p imes d$（如果$B$不是$d$的倍数则方程在整数范围内无解）
则：
$$(acdot d)^x equiv bcdot d (mod (pcdot d))$$
根据等式的性质，一定有
$$ acdot (acdot d)^{x-1}equiv b (mod p)$$
$$ (acdot d)^{x-1}equiv bcdot a^{-1} (mod p)$$
依照上文求解即可
附上SDOI2016计算器的代码
大家不要在意我丧心病狂的写了个trie树当哈希用...
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define LL long long
#define mid (l+r>>1)
#define M 1020000
using namespace std;
LL read(){
LL nm=0,fh=1;char cw=getchar();
for(;!isdigit(cw);cw=getchar()) if(cw=='-') fh=-fh;
for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
return nm*fh;
}
LL m,mod,T,tpe,k,tmp,p[M][10],node,hv0,cnt=1,tg[M];
LL qpow(LL x,LL qs){
LL fin=1;
while(qs){
if(qs&1) fin=fin*x%mod;
x=x*x%mod,qs>>=1;
}
return fin;
}
void ins(LL x,LL id){
if(x==0){hv0=max(id,hv0);return;}
LL now=1;
while(x>0){
if(p[now][x%10]==0){
p[now][x%10]=++cnt;
tg[cnt]=-1;
for(LL i=0;i<10;i++) p[cnt][i]=0;
}
now=p[now][x%10],x/=10;
}
tg[now]=max(tg[now],id);
}
LL find(LL x){
if(x==0) return hv0;
LL now=1;
while(x>0){
if(p[now][x%10]==0) return -1;
now=p[now][x%10],x/=10;
}
return tg[now];
}
void init(int x){
if(x==0) return;
for(int i=0;i<=9;i++) init(p[x][i]),p[x][i]=0;
tg[x]=-1;
}
void getans(){
if(tpe==1){printf("%lld
",qpow(k,m));return;}
if(tpe==2){
if((k%mod==0)^(m%mod==0)) puts("Orz, I cannot find x!");
else printf("%lld
",m*qpow(k,mod-2)%mod);
return;
}
init(1),m%=mod,k%=mod,hv0=-1;
if((k==0)^(m==0)){puts("Orz, I cannot find x!");return;}
LL n=sqrt(mod)+1,u;
u=qpow(k,n),cnt=1;
for(LL i=1,now=k;i<=n;i++,now=now*k%mod) ins(now*m%mod,i);
for(LL i=1,now=u;i<=n;i++,now=now*u%mod){
LL tk=find(now);
if(tk==-1) continue;
printf("%lld
",i*n-tk);
return;
}
puts("Orz, I cannot find x!");
}
int main(){
hv0=-1,T=read(),tpe=read(),memset(tg,-1,sizeof(tg));
while(T--){k=read(),m=read(),mod=read(),getans();}
return 0;
}