1636：【例 6】计算器

题目描述

原题来自：SDOI 2011

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

1. 给定 $y, z, p$，计算 $y^z \bmod p$ 的值；
2. 给定 $y, z, p$，计算满足 $x \times y \equiv z \pmod{p}$ 的最小非负整数 $x$；
3. 给定 $y, z, p$，计算满足 $y^x \equiv z \pmod{p}$ 的最小非负整数 $x$。

输入格式

输入包含多组数据。

第一行包含两个正整数 $T, K$ 分别表示数据组数和询问类型（对于一个测试点内的所有数据，询问类型相同）；

以下 $T$ 行每行包含三个正整数 $y, z, p$，描述一个询问。

输出格式

对于每个询问，输出一行答案。

对于询问类型 $2$ 和 $3$，如果不存在满足条件的，则输出 Orz, I cannot find x!，注意逗号与 I 之间有一个空格。

样例

样例输入 #1（询问类型 1）

3 1
2 1 3
2 2 3
2 3 3

样例输出 #1

2
1
2

样例解释 #1

• 类型 1：计算 $y^z \bmod p$。
• 第一组：$2^1 \bmod 3 = 2$
• 第二组：$2^2 \bmod 3 = 4 \bmod 3 = 1$
• 第三组：$2^3 \bmod 3 = 8 \bmod 3 = 2$

样例输入 #2（询问类型 2）

3 2
2 1 3
2 2 3
2 3 3

样例输出 #2

2
1
0

样例解释 #2

• 类型 2：解方程 $x \times y \equiv z \pmod{p}$。
• 第一组：$x \times 2 \equiv 1 \pmod{3}$，解为 $x=2$（因为 $2 \times 2 = 4 \equiv 1 \pmod{3}$）。
• 第二组：$x \times 2 \equiv 2 \pmod{3}$，解为 $x=1$（$1 \times 2 = 2$）。
• 第三组：$x \times 2 \equiv 3 \pmod{3}$，注意 $3 \bmod 3 = 0$，所以方程是 $2x \equiv 0 \pmod{3}$，解为 $x=0$（因为 $2 \times 0 = 0$）。注意 $x$ 可以取 $0$，且 $0$ 是最小非负整数解。

数据范围与提示

对于全部数据：

• $1 \le y, z, p \le 10^9$
• $1 \le T \le 10$
• 保证 $p$ 为质数

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题三个子任务分别对应：

1. 快速幂取模。
2. 线性同余方程（求逆元）。
3. 离散对数（BSGS算法）。

由于 $p$ 是质数，求解较为方便。

任务 1：直接用快速幂计算 $y^z \bmod p$。

任务 2：方程 $x \times y \equiv z \pmod{p}$。如果 $y \equiv 0 \pmod{p}$，则方程化为 $0 \equiv z \pmod{p}$，如果 $z \equiv 0$，则 $x$ 可取任意整数，最小非负整数解为 $0$；否则无解。如果 $y \not\equiv 0 \pmod{p}$，由于 $p$ 是质数，$y$ 有逆元，$x \equiv z \times y^{-1} \pmod{p}$，用扩展欧几里得或费马小定理求逆元（因为 $p$ 是质数，$y^{p-2} \bmod p$ 就是逆元）。注意求最小非负整数解。

任务 3：离散对数问题 $y^x \equiv z \pmod{p}$，用 BSGS算法（Baby-Step Giant-Step）。由于 $p$ 是质数，且 $p \le 10^9$，但 $T \le 10$，可以使用 BSGS。注意特判：

• 如果 $y \equiv 0 \pmod{p}$，则 $y^x \equiv 0$，如果 $z \equiv 0$ 则 $x=1$（因为 $0^1=0$），但 $x=0$ 时 $y^0=1$（如果 $y=0$，$0^0$ 未定义，通常不考虑）。实际上，$y=0$ 时，$x>0$ 则 $y^x=0$，所以如果 $z=0$ 且 $y=0$，则 $x$ 最小为 $1$（如果 $z \neq 0$ 则无解）。
• 如果 $z \equiv 1 \pmod{p}$，则 $x=0$ 是解（因为 $y^0=1$）。
• 一般情况，BSGS 算法步骤：
  1. 设 $m = \lceil \sqrt{p} \rceil$。
  2. 预处理 $y^{0}, y^{1}, \dots, y^{m-1}$ 模 $p$ 的值，存入哈希表（或有序表）。
  3. 计算 $y^{-m}$（即 $y^{m}$ 的逆元）。
  4. 令 $t = z$，对于 $i$ 从 $0$ 到 $m-1$，检查 $t$ 是否在哈希表中，如果在，则找到解 $x = i \times m + j$（其中 $j$ 是对应的指数）。否则令 $t = t \times y^{-m} \bmod p$。
  5. 如果找不到，则无解。

注意 BSGS 算法中 $y$ 和 $p$ 不一定互质，但 $p$ 是质数且 $y \neq 0 \pmod{p}$ 时它们互质，可以求逆元。如果 $y \equiv 0 \pmod{p}$，已经特判。

由于 $p \le 10^9$，$m \approx 31623$，哈希表大小可行。注意使用 unordered_map 或手写哈希以提高速度。