记录编号	577964	评测结果	AAAAAAAAAAAAAAAAAAA
题目名称	[SDOI 2011]计算器	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	0.907 s
提交时间	2022-12-20 09:06:02	内存使用	3.02 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll fst(ll x,ll y,ll mod){
	if (!y)return 1;
	if (y&1)return x*fst(x,y-1,mod)%mod;
	ll p=fst(x,y/2,mod);return p*p%mod;
}
map<ll,int>mp;
int main(){
	freopen ("supercompute.in","r",stdin);
	freopen ("supercompute.out","w",stdout);
	int T,K;scanf("%d%d",&T,&K);
	while(T--){
		ll y,z,p;scanf("%lld%lld%lld",&y,&z,&p);
		y%=p;
		if (K==1){
			printf("%lld\n",fst(y,z,p));
		}
		z%=p;
		if (K==2){
			if (y%p==0){
				if (z==0)printf("0\n");
				else printf("Orz, I cannot find x!\n");
				continue;
			}
			printf("%lld\n",z*fst(y,p-2,p)%p);
		}
		if (K==3){
			if (y%p==0){
				if (z==0)printf("1\n");
				else if (z==1)printf("0\n");
				else printf("Orz, I cannot find x!\n");
				continue;
			}
			ll m=ceil(sqrt(p));mp.clear();
			ll now=z,g=fst(y,m,p);mp[now]=0;
			for (int i=1;i<m;i++){
				now=now*y%p;
				mp[now]=i;
			}
			now=1;bool ok=0;
			for (int i=1;i<=m;i++){
				now=now*g%p;
				if (mp[now]){
					printf("%lld\n",(m*i%p-mp[now]+p)%p);
					ok=1;break;
				}
			}
			if (!ok)printf("Orz, I cannot find x!\n");
		}
	}
}