# BZOJ 2242 SDOI2011 计算器

## 代码

```#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll get_num(){
ll num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = (num << 3) + (num << 1) + c - '0';
return (flag ? -1 : 1) * num;
}
ll y,z,p;
map<ll,ll>mp;
ll quick_pow(ll a,ll b,ll mod){
ll ret = 1;
while(b > 0){
if(b & 1){
ret = ret * a;
ret %= mod;
}
b >>= 1;
a = a * a;
a %= mod;
}
return ret;
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
if(b == 0){
d = a;
x = 1;
y = 0;
return;
}
exgcd(b,a%b,d,x,y);
ll tp = x;
x = y;
y = tp - (a / b) * y;
return;
}
void BSGS(ll y,ll z,ll p){
mp.clear();
y %= p;
if(y == 0 && z == 0){
cout << "1" << endl;
return;
}
else if(y == 0){
cout << "Orz, I cannot find x!" << endl;
return;
}
ll s = ceil(sqrt(p)),t = 1;
mp[1] = s + 1;
for(int i = 1;i < s;++i){
t = t * y;
t = t % p;
if(!mp[t])mp[t] = i;
}
ll v = quick_pow(y,p-s-1,p);
ll ret = 1;
for(ll k = 0;k < s;++k){
int i = mp[ret * z % p];
if(i){
if(i == s + 1)i = 0;
cout << k*s + i << endl;
return;
}
ret = ret * v;
ret %= p;
}
cout << "Orz, I cannot find x!" << endl;
}
int T,K;
ll ans1,ans2;
int main(){
cin >> T >> K;
while(T--){
if(K == 1){
y = get_num();
z = get_num();
p = get_num();
cout << quick_pow(y,z,p) << endl;
}
else if(K == 2){
y = get_num();
z = get_num();
p = get_num();
ll g = __gcd(y,p);
if(z % g)cout << "Orz, I cannot find x!" << endl;
else{
z /= g;
y /= g;
p /= g;
exgcd(y,p,g,ans1,ans2);
ans1 = ans1 * z;
if(ans1 >= 0)
ans1 = ans1 % p;
else
ans1 = (ans1 % p) + p;
ans1 %= p;
cout << ans1 << endl;
}
}
else if(K == 3){
y = get_num();
z = get_num();
p = get_num();
BSGS(y,z,p);
}
}
return 0;
}```