你被要求设计一个计算器完成以下三项任务：

1、给定y、z、p，计算y^z mod p 的值；

2、给定y、z、p，计算满足xy ≡z(mod p)的最小非负整数x；

3、给定y、z、p，计算满足y^x ≡z(mod p)的最小非负整数x。

为了拿到奖品，全力以赴吧！

思路：
对于询问1，快速幂解决

对于询问2，扩展欧几里得解决

对于询问3，采用BSGS算法

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p, a, b;
ll qmul(ll a, ll b, ll mod) {
    ll ans = 0;
    while (b) {
        if (b & 1) {
            ans = (ans + a) % mod;
        }
        a = (a + a) % mod;
        b >>= 1;
    }
    return ans % mod;
}
ll qpow(ll a, ll b, ll mod) {
    ll ans = 1;
    while (b) {
        if (b & 1) {
            ans = (ans * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans % mod;
}

ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1; y = 0;
        return a;
    } else {
        ll d = exgcd(b, a % b, y, x);
        y -= a / b * x;
        return d;
    }
}

ll bsgs(ll a, ll b, ll p) {
    b%=p;a%=p;
    ll n = sqrt(p) + 1;
    map<ll,ll> mp;
    mp.clear();
    ll ans = b%p;
    if (a == 0 && b == 0) return 0;
    if (a == 0 && b != 0) return -1;
    for (int i = 0; i <= n; i++) {
        mp[ans] = i;
        ans = qmul(ans, a, p);
    }
    ans = 1;
    for (int i = 1; i <= n; i++) ans = qmul(ans, a, p);
    ll ret = 1;
    for (int i = 1; i <= n; i++) {
        ret = qmul(ret, ans, p);
        if (mp[ret] != 0) {
            return (ll)i * n - mp[ret];
        }
    }
    return -1;
}

int main() {
    int n, opt;
    ll a, b, p, x, y;
    while (scanf("%d%d", &n, &opt) != EOF) {
        for (int i = 1; i <= n; i++) {
            scanf("%lld%lld%lld", &a, &b, &p);
            if (opt == 1) {
                printf("%lld\n", qpow(a, b, p));
            } else if (opt == 2) {
                ll d = exgcd(a, p, x, y);
                if (b % d != 0) {
                    printf("Orz, I cannot find x!\n");
                } else {
                    x = qpow(a, p - 2, p) * b % p;
                    printf("%lld\n", x);
                }
            } else {
                ll ans = bsgs(a, b, p);
                if (ans == -1) {
                    printf("Orz, I cannot find x!\n");
                } else {
                    printf("%lld\n", ans);
                }
                
            }
        }
    }
    return 0;
}