形式化题目

给定质数 $p$ 和正整数 $y,z$（$1 \leqslant y,z,p \leqslant 10^9$），按询问类型完成下列三件事之一：

1. 计算 $y^z \bmod p$；
2. 求最小非负整数 $x$，满足 $x \cdot y \equiv z \pmod p$；
3. 求最小非负整数 $x$，满足 $y^x \equiv z \pmod p$。

第 2、3 类无解时输出 Orz, I cannot find x!。

本题的三个任务互相独立，但共享同一个关键结构：$p$ 是质数。质数保证了「非零即互质」，这一句话同时打开了任务 2（费马小定理求逆元）和任务 3（BSGS 中 $y^m$ 可逆）的大门。下面逐个任务推导。

正解

思路

任务 1：快速幂。 计算 $y^z \bmod p$ 就是标准的快速幂，Python 内置的三参数 pow(y, z, p) 直接完成，单次 $O(\log z)$。

任务 2：解线性同余方程 $x \cdot y \equiv z \pmod p$。

朴素做法是枚举 $x \in [0, p)$ 逐个验证，$O(p)$ 在 $p \leqslant 10^9$ 下不可行。转成代数消元：

• 若 $y \bmod p \neq 0$：由 $p$ 是质数知 $\gcd(y, p) = 1$，费马小定理给出 $y^{p-1} \equiv 1 \pmod p$，于是逆元为 $y^{p-2}$，方程两边同乘它得
  $$x \equiv z \cdot y^{p-2} \pmod p$$
  这个等价类 $[0, p)$ 内只有一个代表元，就是最小非负解。
• 若 $y \bmod p = 0$：左边 $x \cdot y$ 恒为 $0$，所以 $z \bmod p = 0$ 时任何 $x$ 都是解，最小取 $0$；否则无解。

任务 3：离散对数 $y^x \equiv z \pmod p$（BSGS / 大步小步）。

同样先想朴素：从 $x = 0$ 起逐个乘 $y$ 碰 $z$，$O(p)$ 不可行。BSGS 的核心观察是：把指数 $x$ 拆成两段，使两侧各枚举 $\sqrt p$ 个值，再在中间用哈希表对接。

先处理退化情形，避免逆元讨论失效：

• $z \equiv 1 \pmod p$：$x = 0$ 时 $y^0 = 1$，直接取最小解 $0$；
• $y \equiv 0 \pmod p$：此时 $x \geqslant 1$ 都有 $y^x \equiv 0$，故 $z \equiv 0$ 时解为 $1$，否则无解。

其余情况 $\gcd(y, p) = 1$，$y$ 的任意幂都可逆。取块长 $m = \lfloor\sqrt{p-1}\rfloor + 1$，由费马小定理，若解存在则可落在 $x \in [0, p-1]$ 内，而这段区间能被写成

的形式（$i \cdot m$ 每跨一步前进 $m$，$j$ 在块内向回退）。把 $x = i \cdot m - j$ 代入并用 $y^m$ 的逆元移项：

于是：

• 小步（baby）：枚举 $j = 0 \dots m-1$，把 $z \cdot y^j \bmod p$ 存进哈希表。由于 $x = i\cdot m - j$，同一个值保留最大的 $j$ 才对应最小的 $x$——Python 字典按插入顺序覆盖，从 $j=0$ 到 $m-1$ 顺序写入恰好留下最大 $j$；
• 大步（giant）：枚举 $i = 1, 2, \dots$，查 $y^{i \cdot m}$ 是否在表中，命中即返回 $x = i \cdot m - j$。

最小性：$i$ 每增加 1，$x$ 的候选区间向右平移 $m$ 且互不重叠，所以第一个命中的 $i$ 已保证区间序；再取该块内最大的 $j$，就得到全局最小 $x$。覆盖性：$i$ 走到 $\lceil (p-1)/m \rceil \leqslant m$ 时已覆盖 $x \leqslant p-1$ 的全部取值（$y$ 的阶至多为 $p-1$），代码里多留一档 $i = m+1$ 作为保险，整层扫完仍未命中即无解。

整体流程如下：

flowchart LR
    A["读入 y, z, p"] --> B{"z ≡ 1 mod p ?"}
    B -- 是 --> C["输出 x = 0"]
    B -- 否 --> D{"y ≡ 0 mod p ?"}
    D -- 是 --> E{"z ≡ 0 ?"}
    E -- 是 --> F["输出 x = 1"]
    E -- 否 --> G["Orz"]
    D -- 否 --> H["baby 表: z·y^j, j=0..m-1"]
    H --> I["giant: 查 y^(i·m), i=1.."]
    I -- 命中 --> J["输出 x = i·m - j"]
    I -- 扫完未中 --> G

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 23:20
# update_at: 2026-09-30 23:20

from math import isqrt
from sys import stdin

ORZ = "Orz, I cannot find x!"


def mul_inverse(y: int, z: int, p: int) -> int | None:
    """解 x*y ≡ z (mod p)：返回使 x*y≡z 的最小非负 x，无解返回 None。

    p 是质数，y%p≠0 时费马小定理给出逆元 y^(p-2)；y%p=0 时只有 z%p=0 才有解，
    且任何 x 都行，最小取 0。
    """
    z %= p
    y %= p
    if y == 0:
        return 0 if z == 0 else None
    return z * pow(y, p - 2, p) % p


def discrete_log(y: int, z: int, p: int) -> int | None:
    """解 y^x ≡ z (mod p) 的最小非负 x（BSGS），无解返回 None。

    p 是质数：先特判 z≡1（x=0）与 y≡0，否则 gcd(y,p)=1，
    写 x = i*m - j（i≥1, 0≤j<m），方程改写成 y^(i*m) = z*y^j 分表查找；
    每个 i 对应 x 的一个互不重叠区间，所以首个命中的 i 里取最大的 j 就是最小 x。
    """
    z %= p
    y %= p
    if z == 1:
        return 0  # x=0 时 y^0=1
    if y == 0:
        return 1 if z == 0 else None  # y≡0 时 x≥1 都得 0

    m = isqrt(p - 1) + 1  # 分表块长，覆盖指数范围 [1, p-1]
    baby = {z * pow(y, j, p) % p: j for j in range(m)}  # 同值保留最大的 j，x=i*m-j 才最小
    step = pow(y, m, p)
    cur = step
    for i in range(1, m + 1):
        j = baby.get(cur)
        if j is not None:
            return i * m - j
        cur = cur * step % p
    return None


def solve() -> None:
    it = iter(stdin.buffer.read().split())
    T, K = int(next(it)), int(next(it))
    out: list[str] = []
    for _ in range(T):
        y, z, p = int(next(it)), int(next(it)), int(next(it))
        if K == 1:
            out.append(str(pow(y, z, p)))
        elif K == 2:
            x = mul_inverse(y, z, p)
            out.append(ORZ if x is None else str(x))
        else:
            x = discrete_log(y, z, p)
            out.append(ORZ if x is None else str(x))
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 23:47
 * update_at: 2026-10-05 23:47
 */
// 一本通 6.4 例 6 计算器：p 为质数，三问分治。
// 任务 1 快速幂；任务 2 费马小定理求逆元解线性同余方程；任务 3 BSGS 求最小离散对数。
#include <cstdio>
#include <map>
#include <cmath>

typedef long long ll;

ll y, z, p; // 每组询问的三个数

// 快速幂 a^b % mod，乘法时先转 __int128 防止溢出（a,b < 1e9，相乘达 1e18 超出 ll 安全范围不大但稳妥）
ll qpow(ll a, ll b, ll mod) {
    ll res = 1 % mod; // mod 可能为 1，答案取 0
    a %= mod;
    while (b > 0) {
        if (b & 1) res = (__int128)res * a % mod;
        a = (__int128)a * a % mod;
        b >>= 1;
    }
    return res;
}

// 任务 2：求最小非负 x 满足 x * y ≡ z (mod p)，p 是质数
void solve2() {
    if (y % p == 0) {
        // 左边恒为 0：z ≡ 0 时任何 x 都是解，最小取 0；否则无解
        if (z % p == 0)
            printf("0\n");
        else
            printf("Orz, I cannot find x!\n");
        return;
    }
    // gcd(y, p) = 1，费马小定理：逆元为 y^(p-2)
    ll inv = qpow(y, p - 2, p);
    printf("%lld\n", z % p * inv % p);
}

// 任务 3：求最小非负 x 满足 y^x ≡ z (mod p)，BSGS 大步小步
void solve3() {
    if (z % p == 1 % p) {
        // y^0 = 1，x = 0 是最小解（p=1 时 z%1=0=1%1 同理）
        printf("0\n");
        return;
    }
    if (y % p == 0) {
        // x >= 1 时 y^x ≡ 0，只有 z ≡ 0 有解且最小为 1
        if (z % p == 0)
            printf("1\n");
        else
            printf("Orz, I cannot find x!\n");
        return;
    }
    // 此时 gcd(y, p) = 1，y^m 可逆，可安全移项
    // x = i*m - j：小步枚举 j 存 z*y^j，大步枚举 i 查 y^(i*m)
    ll m = (ll)sqrt((double)(p - 1)) + 1; // 块长约 sqrt(p)
    std::map<ll, ll> baby; // baby[v] = 使 z*y^j ≡ v 的最大 j（j 越大 x 越小）
    ll cur = z % p;        // cur = z * y^j % p
    for (ll j = 0; j < m; ++j) {
        baby[cur] = j;     // 顺序写入，同值后被更大的 j 覆盖
        cur = (__int128)cur * y % p;
    }
    ll step = qpow(y, m, p);      // 大步长 y^m
    ll giant = 1;                 // giant = y^(i*m) % p
    for (ll i = 1; i <= m + 1; ++i) { // 覆盖 x ∈ [0, p-1] 的全部取值
        giant = (__int128)giant * step % p;
        if (baby.find(giant) != baby.end()) {
            printf("%lld\n", i * m - baby[giant]);
            return;
        }
    }
    printf("Orz, I cannot find x!\n");
}

int main() {
    int T, K;
    scanf("%d %d", &T, &K);
    for (int t = 1; t <= T; ++t) {
        scanf("%lld %lld %lld", &y, &z, &p);
        if (K == 1)
            printf("%lld\n", qpow(y, z, p));
        else if (K == 2)
            solve2();
        else
            solve3();
    }
    return 0;
}

复杂度

三个任务各一次询问的计算量为：任务 1 $O(\log z)$，任务 2 一次快速幂 $O(\log p)$，任务 3 建表与扫描各 $O(\sqrt p)$ 次模乘，空间 $O(\sqrt p)$。$T \leqslant 10$，总计约 $10 \times 3\times 10^4$ 次模乘，Python 下远在时限之内。

总结

• 质数 $p$ 是全部三个任务的共同支点：任务 2 靠费马小定理把「解方程」变成「乘逆元」，任务 3 靠 $\gcd(y,p)=1$ 保证 $y^m$ 可逆、方程能左右改写。
• BSGS 的两个正确性细节最容易写错：一是 baby 表同值要保留最大 $j$（$x = i\cdot m - j$，$j$ 越大 $x$ 越小）；二是 $i$ 的候选区间互不重叠，首个命中的 $i$ 才给出最小 $x$。本次实现初期把两侧公式写反（表存 $y^j$ 却拿 $y^{-j}$ 查），在真实数据 calc12 上暴露为「答案偏小的假解」，已按标准形式修正。
• 退化情形要先行处理：$z \equiv 1$（解为 0）、$y \equiv 0$（任务 2 中 $z\equiv 0$ 解为 0 / 任务 3 中 $z\equiv 0$ 解为 1），否则逆元推导对 $y \equiv 0$ 失效。