模运算计算器

题目描述

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

任务1： 给定 $Y, Z, P$，计算 $Y^Z \pmod{P}$ 的值；

任务2： 给定 $Y, Z, P$，计算满足 $xY \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 \le Y, Z, P \le 10^9$，其中 $P$ 为质数
• $1 \le T \le 10$

输入样例

3 1
2 1 3
2 2 3
2 3 3

输出样例

2
1
2

样例解释

样例1：$K=1$（快速幂计算）

1. 第一组：$Y=2, Z=1, P=3$，计算 $2^1 \mod 3 = 2$
2. 第二组：$Y=2, Z=2, P=3$，计算 $2^2 \mod 3 = 4 \mod 3 = 1$
3. 第三组：$Y=2, Z=3, P=3$，计算 $2^3 \mod 3 = 8 \mod 3 = 2$

其他类型示例（非样例数据）

类型2示例（乘法逆元）：$Y=3, Z=2, P=7$

• 需要解 $3x \equiv 2 \pmod{7}$
• 即 $x \equiv 2 \times 3^{-1} \pmod{7}$
• 由于 $3 \times 5 = 15 \equiv 1 \pmod{7}$，所以 $3^{-1} \equiv 5 \pmod{7}$
• $x \equiv 2 \times 5 = 10 \equiv 3 \pmod{7}$
• 最小非负整数解为 $3$

类型3示例（离散对数）：$Y=2, Z=3, P=5$

• 需要解 $2^x \equiv 3 \pmod{5}$
• 计算：$2^1=2, 2^2=4, 2^3=8\equiv3 \pmod{5}$
• 所以最小解为 $x=3$

三个任务详解

任务1：快速幂取模

计算 $Y^Z \mod P$

• 使用快速幂算法，时间复杂度 $O(\log Z)$
• 注意使用 long long 防止溢出

任务2：线性同余方程

解方程 $xY \equiv Z \pmod{P}$

• 由于 $P$ 是质数，$Y$ 在模 $P$ 下有乘法逆元当且仅当 $Y \not\equiv 0 \pmod{P}$
• 如果 $Y \equiv 0 \pmod{P}$：
  • 如果 $Z \equiv 0 \pmod{P}$，则任意 $x$ 都满足，最小非负整数解为 $0$
  • 如果 $Z \not\equiv 0 \pmod{P}$，则无解
• 如果 $Y \not\equiv 0 \pmod{P}$：
  • 使用费马小定理求逆元：$Y^{-1} \equiv Y^{P-2} \pmod{P}$
  • 解为 $x \equiv Z \times Y^{P-2} \pmod{P}$

任务3：离散对数（Baby-step Giant-step算法）

解方程 $Y^x \equiv Z \pmod{P}$

• 特殊情况：
  • 如果 $Y \equiv 0 \pmod{P}$：
    • 如果 $Z \equiv 0 \pmod{P}$，则 $x=1$（$0^1=0$）
    • 如果 $Z \not\equiv 0 \pmod{P}$，则无解
  • 如果 $Y \equiv 1 \pmod{P}$：
    • 如果 $Z \equiv 1 \pmod{P}$，则 $x=0$（$1^0=1$）
    • 如果 $Z \not\equiv 1 \pmod{P}$，则无解
• 一般情况：使用 Baby-step Giant-step 算法
  • 设 $m = \lceil \sqrt{P} \rceil$
  • 预计算 $Y^0, Y^1, ..., Y^{m-1}$ 并存入哈希表
  • 计算 $Y^{-m} = (Y^{P-2})^m \mod P$（费马小定理）
  • 对于 $i = 0, 1, ..., m$，计算 $Z \times (Y^{-m})^i$ 并在哈希表中查找

时空限制

• 时间限制：1秒
• 空间限制：64MB