G22 扩展 BSGS 算法

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL exBSGS(LL a,LL b,LL p)
{
	a%=p;b%=p;if(b==1 || p==1) return 0;
	LL ak=1%p,k=0,d;//对比BSGS：需要得到ak 和 k
	while( (d=__gcd(a,p))!=1 ) 
	{
		if(b%d)return -1;
		ak=ak*(a/d)%(p/d);
		k++;b/=d;p/=d;
		if(ak==b) return k;
	}
	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=ak;i<=m;i++)if( f.count(t=t*am%p) ) return i*m-f[t]+k;// 对比BSGS：+k
	return -1;
}
int main() 
{
	LL a,b,p;//解决 a^x % p=b
	while(scanf("%lld%lld%lld",&a,&p,&b)!=EOF &&a &&b &&p) 
	{
		LL ans=exBSGS(a,b,p);
		if(ans!=-1)printf("%lld\n",ans);
		else printf("No Solution\n");
	}
	return 0;
}

G22 扩展 BSGS 算法

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL exBSGS(LL a,LL b,LL p)
{
	a%=p;b%=p;if(b==1 || p==1) return 0;
	LL ak=1%p,k=0,d;//对比BSGS：需要得到ak 和 k
	while( (d=__gcd(a,p))!=1 ) 
	{
		if(b%d)return -1;
		ak=ak*(a/d)%(p/d);
		k++;b/=d;p/=d;
		if(ak==b) return k;
	}
	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=ak;i<=m;i++)if( f.count(t=t*am%p) ) return i*m-f[t]+k;// 对比BSGS：+k
	return -1;
}
int main() 
{
	LL a,b,p;//解决 a^x % p=b
	while(scanf("%lld%lld%lld",&a,&p,&b)!=EOF &&a &&b &&p) 
	{
		LL ans=exBSGS(a,b,p);
		if(ans!=-1)printf("%lld\n",ans);
		else printf("No Solution\n");
	}
	return 0;
}