```cpp
int T, k;
unordered_map<ll, ll> mpp;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if(!b) return (x = 1, y = 0), a;
ll t = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return t;
}
ll BSGS(ll x, ll y, ll mod) {
mpp.clear();
y %= mod;
if(!x && !y) return 1;
else if(!x) return -1;
int times = sqrt(mod) + 1;
rep(i, 0, times - 1) mpp[y * qpow(i, x, mod) % mod] = i;
x = qpow(times, x, mod);
rep(i, 1, times) {
ll now = qpow(i, x, mod);
ll nowval = mpp.find(now) == mpp.end() ? -1 : mpp[now];
if(~nowval && ~(i * times - nowval)) return i * times - nowval;
}
return -1;
}
int main() {
qread(T, k);
if(k == 1) {
W(T) {
ll y, z, mod;
qread(y, z, mod);
printf("%lld\n", qpow(z, y, mod) % mod);
}
}
else if(k == 2) {
W(T) {
ll y, z, mod;
ll a, b;
qread(y, z, mod);
ll t = exgcd(y, mod, a, b);
if(z % t) puts("Orz, I cannot find x!");
else {
ll tmp = mod / t;
while(!(~a)) a += tmp;
printf("%lld\n", ((a * z / t) % mod + mod) % mod);
}
}
}
else {
W(T) {
ll y, z, mod;
qread(y, z, mod);
ll ans = BSGS(y, z, mod);
ans == -1 ? puts("Orz, I cannot find x!") : printf("%lld\n", ans);
}
}
return 0;
}
```
by Ryo_Yamada @ 2020-11-28 23:02:47
BSGS？
by _SkyBlue @ 2020-11-28 23:04:09
@[_SkyBlue](/user/250147) 是的 QAQ
by Ryo_Yamada @ 2020-11-28 23:06:30
~~为什么不尝试用一下逆元呢~~
```
void Solve(int y,int z,int p){
if(y%p==0&&z%p)
puts("Orz, I cannot find x!");
else
printf("%lld\n",1ll*fpow(y,p-2,p)*z%p);
}
```
by 是个汉子 @ 2020-11-28 23:35:08
前来对dva进行考咕
by 在中路数星星ε @ 2021-09-09 23:06:25