C++14(g++5.4) 解法, 执行用时: 274ms, 内存消耗: 2512K, 提交时间: 2019-08-26 14:58:16

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ksm(ll x,ll y,ll p){
	ll res=1;
	while(y){
		if(y&1)
			res=res*x%p;
		x=x*x%p;
		y/=2;
	}
	return res;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(!b){
		x=1;
		y=0;
		return a;
	}
	ll d=exgcd(b,a%b,x,y);
	ll t=x;
	x=y;
	y=t-y*(a/b);
	return d;
}
ll bsgs(ll a,ll b,ll p){
	map<ll,ll>hash;
	hash.clear();
	b%=p;
	int t=(int)sqrt(p)+1;
	for(int j=0;j<t;j++){
		int val=(ll)b*ksm(a,j,p)%p;
		hash[val]=j;
	}
	a=ksm(a,t,p);
	if(a==0){
		if(b==0)
			return 1;
		else return -1;
	}
	for(int i=0;i<=t;i++){
		ll val=ksm(a,i,p);
		int j=hash.find(val)==hash.end()?-1:hash[val];
		if(j>=0&&j*t-j>=0)
			return i*t-j;
	}
	return -1;
}
int main(){
	int T,k;
	scanf("%d%d",&T,&k);
	while(T--){
		ll y,z,p;
		scanf("%lld%lld%lld",&y,&z,&p);
		if(k==1){
			printf("%lld\n",ksm(y,z,p));
		}
		else if(k==2){
			ll x=0,y1=0;
			ll d=exgcd(y,p,x,y1);
			//printf("%d\n",d);
			if(z%d!=0){
				printf("Orz, I cannot find x!\n");
				continue;
			}
			x=x*z/d;
			ll p1=p/d;
			x=(x%p1+p1)%p1;
			printf("%lld\n",x);
		}
		else{
			ll ans=bsgs(y,z,p);
			if(ans==-1)
				printf("Orz, I cannot find x!\n");
			else
				printf("%lld\n",ans);
		}
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 117ms, 内存消耗: 3576K, 提交时间: 2020-10-10 14:48:45

#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int t,k,y,z,p,d,ax,ay,A,ph,prod;
map<int,int>ba;
bool euc(int a,int b,int &x,int &y){
	if(!b)
		if(z%a)return false;
		else x=1,y=0,d=a;
	else if(euc(b,a%b,y,x))y-=x*(a/b); 
		else return false;
	return true;
}int main(){
	for(scanf("%d%d",&t,&k);t--;){
		scanf("%d%d%d",&y,&z,&p);
		if(k==1){
			prod=1,y%=p;
			for(;z;z>>=1,y=1ll*y*y%p)
				if(z&1)prod=1ll*prod*y%p;
			printf("%d",prod);
		}else if(k==2){
			z%=p;
			if(euc(y,p,ax,ay))
				A=p/d,printf("%lld",((1ll*ax*z/d)%A+A)%A);
			else goto lose;
		}else if(k==3){
			if(z==1){
				putchar('0');
				goto end;
			}if(!(y%p)){
				if(z==0){
					putchar('1');
					goto end;
				}else goto lose;
			}ph=ceil(sqrt(p-1)),A=prod=1,ba.clear();
			for(int i=1;i<=ph;i++)
				prod=1ll*prod*y%p,ba[1ll*prod*z%p]=i;
			for(int i=1;i<=ph;i++){
				A=1ll*A*prod%p;
				if(ba[A]){
					printf("%d",i*ph-ba[A]);
					goto end;
				}
			}lose:printf("Orz, I cannot find x!");
		}end:putchar('\n');
	}return 0;
}