G21 BSGS 算法

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL BSGS(LL a,LL b,LL p)
{
	a%=p;b%=p;if(b==1)return 0;
	LL m=ceil(sqrt(p)),am=1;
	unordered_map<LL,LL>f;
	for(LL j=1;j<=m;j++)f[ b*(am=am*a%p)%p ]=j;
	for(LL i=1,t=1;i<=m;i++)if( f.count(t=t*am%p) )return i*m-f[t];
	//map.count(Key)返回值为1或者0，1返回存在，0返回不存在		
	return -1;
}
int main()
{
	LL a,b,p;
	while(scanf("%lld%lld%lld",&p,&a,&b)!=EOF)
	{
		LL ans=BSGS(a,b,p);
		if(ans==-1) printf("no solution!\n");
		else printf("%lld\n",ans);
	}
	return 0;
}