做一下两年前 litble 就 AC 的题，复习 BSGS（这就是你 H₂O 博客的理由？）

https://www.mina.moe/BZPRO/JudgeOnline/2242.html

$K = 1$

快速幂即可

$K = 2$

并不需要扩欧（我脱欧我自豪）

$$ax \equiv b \mod p$$
$$x = ba ^ {-1} \mod p$$
快速幂费马小定理求逆元即可

$K = 3$

BSGS 即可

注意特判 $a ^ x \equiv b \mod p$中 $a \mod p = 0$的情况

#include <bits/stdc++.h>

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int T, K, Y, Z, P;

map<int, int> mp;

int qpow(int a, int b, int p)
{
    a %= p;
    int res = 1;
    while (b)
    {
        if (b & 1) res = 1ll * res * a % p;
        a = 1ll * a * a % p, b >>= 1;
    }
    return res % p;
}

int main(int argc, char const* argv[])
{
    IN(T), IN(K);
    while (T--)
    {
        IN(Y), IN(Z), IN(P);
        if (K == 1) printf("%d\n", qpow(Y, Z, P));
        else if (K == 2)
        {
            Y %= P, Z %= P;
            if (!Y) puts("Orz, I cannot find x!");
            else
            {
                Y = qpow(Y, P - 2, P);
                printf("%lld\n", 1ll * Z * Y % P);
            }
        }
        else
        {
            Y %= P, Z %= P, mp.clear();
            if (!Y)
            {
                if (!Z) puts("1");
                else puts("Orz, I cannot find x!");
                continue;
            }
            int k = 1, dt = 1, m = ceil(sqrt(P));
            for (int i = 0; i <= m; i += 1, k = 1ll * k * Y % P)
                mp[(int)(1ll * k * Z % P)] = i + 1, dt = k;
            k = dt;
            for (int i = 1; i <= m; i += 1, k = 1ll * k * dt % P)
                if (mp[k]) {printf("%d\n", i * m - mp[k] + 1); goto end;}
            puts("Orz, I cannot find x!");
            end : continue;
        }
    }
    return 0;
}