QNDJR
巨佬爆切省选啊
by Aw顿顿 @ 2020-03-16 16:09:57
终于 AC 了！
代码：
```cpp
#include <iostream>
#include <unordered_map>
#include <cmath>
using namespace std;
typedef long long ll;
unordered_map<ll, ll> mp;
inline ll quick_pow(ll x, ll p, ll mod){
ll ans = 1;
while (p){
if (p & 1) ans = ans * x % mod;
x = x * x % mod;
p >>= 1;
}
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), temp = x;
x = y;
y = temp - a / b * y;
return gcd;
}
inline ll BSGS(ll a, ll b, ll p){
a %= p;
b %= p;
if (b == 1) return 0;
if (a == 0) return b == 0 ? 1 : -1;
ll m = sqrt(p) + 1, x, y = 1, z;
mp.clear();
x = b;
z = quick_pow(a, m, p);
mp[x] = 0;
for (register ll i = 1; i < m; i++){
x = x * a % p;
mp[x] = i;
}
for (register ll i = 1; i <= m; i++){
y = y * z % p;
if (mp.count(y)){
return i * m - mp[y];
}
}
return -1;
}
int main(){
int t, k;
cin >> t >> k;
for (register int i = 1; i <= t; i++){
int y, z, p;
cin >> y >> z >> p;
if (k == 1){
cout << quick_pow(y, z, p) << endl;
} else if (k == 2){
y %= p;
z %= p;
if (y == 0 && z != 0){
cout << "Orz, I cannot find x!" << endl;
} else {
cout << z * quick_pow(y, p - 2, p) % p << endl;
}
} else {
ll ans = BSGS(y, z, p);
if (ans == -1){
cout << "Orz, I cannot find x!" << endl;
} else {
cout << ans << endl;
}
}
}
return 0;
}
```
by Leasier @ 2020-03-17 09:36:21
@[Leasier](/user/201007) 为什么我总能抓到leasier大佬
by sail_with_pleasure @ 2023-02-08 10:48:43