http://poj.org/problem?id=3243
这道题的输入数据输入后需要将a和b都%p
https://blog.csdn.net/zzkksunboy/article/details/73162229
在大约sqrt( p )的复杂度求出 ( a^x ) % p = b % p中的x
扩展bsgs增加了对p不是素数的情况的处理。
扩展bsgs在处理过a,b,p之后进行bsgs的时候x处理不到num以下的部分，这部分在处理a,b,p的时候处理过了（b=1输出num）所以不用考虑。
所以实际上扩展bsgs和普通bsgs只多了一个处理的循环部分。
ac一次之后我又把多余的（非预处理循环内的）判定a==b和b==1的情况的部分删除了，也是对的，最开始在这些没必要的部分上纠结真是画蛇添足了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
#define LL long long
LL p,a,b;
map<LL,LL>q;
LL mgcd(LL x,LL y){return y==?x:mgcd(y,x%y);}
int main(){
while(~scanf("%lld%lld%lld",&a,&p,&b)){
if(a==&&p==&&b==)break;b=b%p;a=a%p;
LL x=,y=,t=,d=mgcd(a,p),ff=;
while(d!=){
if(b==){printf("%lld\n",t);ff=;break;}
if(b%d!=){printf("No Solution\n");ff=;break;}
++t;a/=d;b/=d;p/=d;
y=(y*a)%p;a=a*d;
d=mgcd(a,p);
}if(ff)continue;
a%=p;b%=p;
LL w=(LL)sqrt((double)p);if(w*w!=p)++w;
q[b]=-; for(int i=;i<=w;++i){x=(x*a)%p;LL z=(b*x)%p;q[z]=i;}
bool f=;LL m=10000000000000000LL;
for(int i=;i<=w;++i){
y=(y*x)%p;
if(q[y]!=){
LL z=q[y];if(z==-) z=;
z=(LL)i*w-z;f=;
m=min(z+t,m);
}
}
q[b]=;x=;
for(int i=;i<=w;++i){x=(x*a)%p;LL z=(b*x)%p;q[z]=;}
if(!f)printf("No Solution\n");
else printf("%lld\n",m);
}
return ;
}