1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
unordered_map<ll,ll>mp;
ll quick_pow(ll a,ll b,ll c)
{
ll ans = 1;
while(b)
{
if(b&1)ans=(ans*a)%c;
b>>=1;
a=(a*a)%c;
}
return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
ll gcd = exgcd(b,a%b,x,y);
ll temp = x;
x = y;
y = temp - a/b*y;
return gcd;
}
ll solve2(ll a,ll z,ll b)
{ ll x,y;
ll g = exgcd(a,b,x,y);
if(z%g)return -1;
b/=g;
while(x<0)x+=b;
x=((x*z/g)%b+b)%b;
return x;
}
ll bsgs(ll y,ll z,ll p)
{
if(y==0&&z==0)return 1;
if(y==0&&z!=0)return -1;
mp.clear();
ll m = ceil(sqrt(p));
ll now = z%p,f= quick_pow(y,m,p);
mp[now]=0;
for(int i=1;i<=m;i++)
{
now=(now*y)%p;
mp[now]=i;
}
now = 1;
for(int i=1;i*i<=p+1;i++)
{
now = (now*f)%p;
if(mp.count(now))
{
return ((i*m-mp[now])%p+p)%p;
}
}
return -1;
}
int main()
{
ll k,T,y,z,p;
scanf("%lld %lld",&T,&k);
while(T--)
{ scanf("%lld %lld %lld",&y,&z,&p);
if(k==1)
{
printf("%lld\n",quick_pow(y,z,p));
}
else if(k==2)
{
if(solve2(y,z,p)==-1)printf("Orz, I cannot find x!\n");
else printf("%lld\n",solve2(y,z,p));
}
else
{
if(bsgs(y,z,p)==-1||bsgs(y,z,p)==0)printf("Orz, I cannot find x!\n");
else printf("%lld\n",bsgs(y,z,p));
}
}
}
|