思路与算法

K=1用快速幂。K=2先约去模p，底数非零时用费马逆元计算z/y；底数为0时按z是否为0决定最小解0或无解。K=3先处理目标1的x=0及底数0，再对非零底数使用BSGS：存y^j的最小j，逐块检查z*(y^m)^(-i)，首次找到给出i*m+j。

正确性说明

快速幂按二进制分解指数正确。质数模p下非零底数可逆，一次同余有唯一剩余类，0至p-1的代表最小。非零底数的幂周期整除p-1，BSGS把所有可能指数按连续m长度分块，i递增且每个baby值存最小j，所以第一次命中即最小非负指数。底数0与目标0不满足互质前提，单独分支避免错误求逆。

复杂度

每组快速幂/逆元O(log p)，BSGS期望O(√p)时间和空间，哈希表创建、预留与baby表插入均计入；T≤10、p≤10^9。乘积小于10^18，long long安全。不存在时输出固定英文。

易错点

y和z可能是p的倍数，必须先取模。K=3目标1时x=0即使y为0也按0次乘法得到1；目标0且y非零则无解。独立小模数遍历完整幂周期，大模数样例选可逐次乘到首个命中的指数，证明最小性，不依赖另一个BSGS。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
long long power(long long a, long long e, long long p) {
    long long r = 1 % p;
    for (a %= p; e; e /= 2, a = a * a % p)
        if (e & 1)
            r = r * a % p;
    return r;
}
long long logDiscrete(long long y, long long z, long long p) {
    y %= p;
    z %= p;
    if (z == 1)
        return 0;
    if (y == 0)
        return z == 0 ? 1 : -1;
    if (z == 0)
        return -1;
    long long m = sqrtl(p) + 1;
    unordered_map<long long, long long> baby;
    baby.reserve(m * 2);
    long long a = 1;
    for (long long j = 0; j < m; ++j) {
        baby.emplace(a, j);
        a = a * y % p;
    }
    long long factor = power(a, p - 2, p), value = z;
    for (long long i = 0; i <= m; ++i) {
        auto it = baby.find(value);
        if (it != baby.end())
            return i * m + it->second;
        value = value * factor % p;
    }
    return -1;
}
int main() {
    int T, K;
    cin >> T >> K;
    while (T--) {
        long long y, z, p;
        cin >> y >> z >> p;
        long long result;
        if (K == 1)
            result = power(y, z, p);
        else if (K == 2) {
            y %= p;
            z %= p;
            result = y == 0 ? (z == 0 ? 0 : -1) : z * power(y, p - 2, p) % p;
        } else
            result = logDiscrete(y, z, p);
        if (result < 0)
            cout << "Orz,I cannot find x!\n";
        else
            cout << result << '\n';
    }
}