\(非常简单的一道板子训练题\)
\(对于问题一：直接使用快速幂解决\)
\(对于问题二：使用exgcd解决\)
\(对于问题三：使用bsgs解决\)
\(code:\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define pii pair<int,int>
using namespace std;
//const int mod=998244353;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; };
int qpw(int a, int b, int mod) {
int ans = 1;
while (b) {
if (b & 1)ans = ans * a % mod;
a = a * a % mod, b >>= 1;
}
return ans;
}
int inv(int x, int mod) { return qpw(x, mod - 2, mod); }
int exgcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int bsgs(int a,int b,int mod){
a%=mod,b%=mod;
if(b==1)return 0;
if(a==0&&b==0)return 1;
if(a==0&&b!=0)return -1;
unordered_map<int,int>mp;
int m=ceil(sqrt(mod)),t=b;
mp[b]=0;
for(int j=1;j<m;j++){
t=t*a%mod;
mp[t]=j;
}
int mi=1;
for(int i=1;i<=m;i++){
mi=mi*a%mod;
}
t=1;
for(int i=1;i<=m;i++){
t=t*mi%mod;
if(mp.count(t)){
return i*m-mp[t];
}
}
return -1;
}
int op;
void solve() {
int y,z,p;
cin>>y>>z>>p;
if(op==1){
cout<<qpw(y,z,p)<<'\n';
}else if(op==2){
int gc=gcd(y,p);
if(z%gc){
cout<<"Orz, I cannot find x!"<<'\n';
}else {
int X,Y;
exgcd(y,p,X,Y);
X=(X*z%p+p)%p;
cout<<X<<'\n';
}
}else {
int x=bsgs(y,z,p);
if(x==-1){
cout<<"Orz, I cannot find x!"<<'\n';
}else cout<<(x%p+p)%p<<'\n';
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int _ = 1;
cin >> _;cin>>op;
while (_--)solve();
}