#include<cstdio>
#include<iostream>
#include<map>
#include<cmath>
#define ll long long
using namespace std;
ll T,k,y,z,p;
map<int,int> mp;
void exgcd(int a1,int a2,ll &x,ll &y)
{
if(!a2)
{
x=;
y=;
return;
}
exgcd(a2,a1%a2,x,y);
int t=x;
x=y;
y=t-a1/a2*y;
}
ll gcd(ll a1,ll a2)
{
for(;a2;)
{
ll a3=a1%a2;
a1=a2;
a2=a3;
}
return a1;
}
ll kuai(ll y,ll z)
{
ll ans=;
for(;z;)
{
if(z%)
ans=(ans*y)%p;
y=(y*y)%p;
z=z/;
}
return ans;
}
bool pan(ll y,ll z,ll p)
{
mp.clear();
ll m=ceil(sqrt(p)),t=;
mp[]=m+;
for(ll i=;i<m;i++)
{
t=t*y%p;
mp[t]=i;
}
ll T=kuai(y,p-m-),ine=;
for(int k=;k<=m;k++)
{
int i=mp[z*ine%p];
if(i)
{
if(i==m+)
i=;
printf("%lld\n",k*m+i);
return ;
}
ine=ine*T%p;
}
return ;
}
int main()
{
scanf("%lld%lld",&T,&k);
for(int i=;i<=T;i++)
{
scanf("%lld%lld%lld",&y,&z,&p);
if(k==)
printf("%lld\n",kuai(y,z));
if(k==)
{
ll x1,y1;
ll t=gcd(y,p);
if(z%t)
{
printf("Orz, I cannot find x!\n");
continue;
}
y/=t;
p/=t;
z/=t;
exgcd(y,p,x1,y1);
x1=(x1*z)%p;
for(;x1<;)
x1+=p;
printf("%lld\n",x1);
}
if(k==)
{
y%=p;
z%=p;
if(!y&&!z)
{
printf("1\n");
continue;
}
if(!y)
{
printf("Orz, I cannot find x!\n");
continue;
}
if(!pan(y,z,p))
printf("Orz, I cannot find x!\n");
}
}
return ;
}
第一种情况 快速幂 第二种情况 exgcd 第三种情况 大步小步法 把x变成k*m+i，把所有的0-m次方用map存下来，然后依次累加k，直到找到一个可行的。