学完才发现其实并没有那么复杂，但中间还是有很多地方困扰了我很久orz；
先安利一名神犇的博客：BSGS；
首先，大步小步的思想有点像分块，将整体划分成根号n块，再对每一小块中的根号n种取值找一个最优值；
如果看完了我安利的那篇博客的话，应该是能够自己写出随处取逆元的写法了；
但是这样的做法太慢，考虑怎么把取逆元的过程除去；
首先定义一下符号，求下式的最小整数解
那篇博客中也提到了如何将非扩展大步小步的逆元怎么消掉，这里也就不再赘述；
而对于模数与a不互质的情况，实际上神犇给的代码是有这种优化的，但没有详细讲，导致我懵逼了很久；
首先，那篇文章中提到，当b’=1时，可以直接返回答案，但是b’是需要用逆元来算的，所以可以将要算的逆元乘过去，改成当b/g=a/g时，即可返回；
但这样又有一个问题，本来判断不合法的时候需要判断b能否被gcd（a,p）整除，如果不去算每一步的b的话，能否成立呢？
这里从一开始推的地方再推一遍就能知道；
a^x=b(mod p),设g=gcd(a,p），如果g==1的话a，p互质，直接用下一步计算即可；
如果不互质，设a^x+kp=b;
两边同除g
得 a/g*a^(x-1)+k*p/g=b/g；
原文中是将这一个式子改成在模p/g意义下，那么就能得到一个新式子；
而这一步有解的条件是，b/g是整数，否则无解；
到下一步的新式子的时候，由于不想在逆元的条件下进行运算，
先设p’=p/g,下一步式子为a/g*a^(x-1)=b/g(mod p’)；
再展开为普通的形式： a/g*a^(x-1)+k*p’=b/g;
取g’=gcd( a , p’)，再两边同除g’就可以发现，下一步式子有解的条件是b/g能够被g’整除；
这里就可以发现，如果想要判断是否有解，只需要判断b/g是否能被g’整除，完全不用把b’用逆元求出来，只需要把每次要除的数乘到一起，化到最后能够直接利用BSGS的最简形式为
a^t/(∏g)*a^(x-t)=b/(∏g)(mod p/(∏g));(LaTex不大会用只能这样了。。。）
这样全程没用逆元就可以求了；
接下来是代码：
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<map>
#define LL long long
#define random(a,b) (a+rand()%(b-a+1))
LL gcd(LL a,LL b)
{
return b==0 ? a: gcd(b,a%b);
}
//LL hamod=999983;无视我丑爆还出错的哈希吧qwq
//LL hashmap[1000000];
/*LL hash(LL x) { //LL tp=x; return x*1349880437ll%hamod; }*/
std::map<LL,LL>hash;
LL pow(LL x,LL y,LL mo)
{
LL ans=1;
for(;y;y>>=1,x=(LL)x*x%mo)if(y&1)ans=(LL)ans*x%mo;
return ans;
}
LL bsgs(LL a,LL b,LL mo)
{
a%=mo,b%=mo;
if(a==0)return b ? -1 : 1 ;
if(b==1||mo==1)return 0;//特判一波，注意模数可能为1
LL cnt=0;
LL t=1;
for(LL g=gcd(a,mo);g!=1;g=gcd(a,mo))
{
if(b%g)return -1;//如果不符合条件，返回；
cnt++;
mo/=g,b/=g,t=(LL)(t*a/g)%mo;//将每次要除的数累加到一个变量里；
if(b==t)return cnt;
}
LL sq=(int)(std::sqrt((double)mo)+1);//上取整开根
LL di=b;//求大步小步时等号右边的那个b；
hash.clear();
// memset(hashmap,0,sizeof(hashmap));
for(LL i=1;i<=sq;i++)//由于我一开始用的哈希是要从1开始而且好写，所以后来统计答案的时候都平移了一下；
{
// hashmap[hash(di)]=i;
hash[di]=i;//这里的di其实是b*a^(i-1),因为我平移了一下嘛。。。
di=(LL)di*a%mo;
}
di=pow(a,sq,mo);//求a^sq，大步中每一次跳的大小
for(LL i=1;i<=sq+1;i++)
{
t=(LL)t*di%mo;//因为这里是用大块减去小块来求值，所以第一次求的时候就要把第一个大块算上（我也不知道我在口胡啥，还是看神犇的博客吧。。。）
//t是之前累加的等号右边要除的东西，现在直接在等号左边乘起来
if(hash.count(t))return cnt+i*sq-(hash[t]-1);//之前说好的要平移一波。。。
}
return -1;
}
LL a,b,mo;
int main()
{
scanf("%lld%lld%lld",&a,&mo,&b);
while(a||b||mo)
{
LL ans=bsgs(a,b,mo);
if(ans==-1)printf("No Solution\n");
else printf("%lld\n",ans%mo);
scanf("%lld%lld%lld",&a,&mo,&b);
}
return 0;
} 其实，码完这些我才发现，判断可行性好像只要一开始判断一次就可以，那么我上边说的就全是废话了。。。