[SDOI]2011计算器

archer233 / 2024-11-17 / 原文

$非常简单的一道板子训练题$
$对于问题一：直接使用快速幂解决$
$对于问题二：使用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();
}