自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:39:14，当前版本为作者最后更新于2022-08-04 11:33:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P8457 「SWTR-8」幂塔方程

题目描述

如果小 A 是一个，一个一个一个毒瘤，他会让你求解套了十层甚至九层娃的幂塔方程，但他不是。

他想让你求解：

$$x ^ x\equiv D \pmod n$$

保证 $n$ 的最大质因子不超过 $10 ^ 5$，且 $D$ 与 $n$ 互质。

你需要保证得到的解 $x$ 为 $[0, 2 ^ {125}]$ 范围内的整数。若该范围内无解，输出 $-1$；若存在多解，输出任意一个。

多组测试数据。

数据范围

• Subtask #1（5 points）：$n\leq 20$。
• Subtask #2（8 points）：$n\leq 400$。依赖 Subtask #1。
• Subtask #3（11 points）：$n$ 是质数，$T\leq 10 ^ 4$。
• Subtask #4（15 points）：$\mu(n) \neq 0$，$T\leq 100$。
• Subtask #5（9 points）：$\mu(n) \neq 0$，$T\leq 10 ^ 4$。依赖 Subtask #4。
• Subtask #6（13 points）：$n = p ^ k(p \in \mathrm{prime})$，$T\leq 100$。
• Subtask #7（7 points）：$n = p ^ k(p \in \mathrm{prime})$，$T\leq 10 ^ 4$。依赖 Subtask #3，#6。
• Subtask #8（6 points）：$m\leq 1064$。依赖 Subtask #2。
• Subtask #9（16 points）：$n\leq 10 ^ 9$，$T\leq 10 ^ 4$。
• Subtask #10（10 points）：无特殊限制。依赖 Subtask #5，#7，#8，#9。

对于 $100\%$ 的数据：

• $1\leq T\leq 4\times 10 ^ 4$。
• $2\leq n \leq 10 ^ {18}$。
• $1\leq D < n$，$D\perp n$。
• $2\leq p_1 < p_2 < \cdots < p_k \leq 10 ^ 5$。

Sol 0

验题人 chenxia25 给出了一个假做法：将 $n$ 分解质因数，对于每个 $p ^ k$ 可以单独求解。然后 excrt 合并。

问题在于 $p ^ k$ 很大，且 $p ^ k \times \varphi(p ^ k)$ 可能不互质，但对于单独求解的 $p ^ k$ 得到的解互质（因为有多解），导致同余方程合并时无解。

Sol 1

考虑 $n = p$。

令 $x_1$ 为 $x \equiv D \pmod p$ 和 $x \equiv 1 \pmod {p - 1}$ 的解，容易发现 $x_1$ 存在。

Sol 2

考虑 $n = p ^ k$。

考虑 增量法构造。

设 $x_i ^ {x_i} \equiv D \pmod {p ^ i}$。考虑如何 $x_i$ 推到 $x_{i + 1}$。

容易发现令 $x_i \gets x_i + Ip ^ i(p - 1)$ 仍然可行，因此设 $x_{i + 1} = x_i + Ip ^ i(p - 1)$。

考虑求出 $I$。因为 $x_{i + 1} ^ {x _{i + 1}} \equiv D \pmod {p ^ {i + 1}}$，所以 $(x_i + Ip ^ i(p - 1)) ^ {x_i + Ip ^ i(p - 1)} \equiv D \pmod {p ^ {i + 1}}$。

因为 $D$ 和 $p ^ i$ 互质，所以 $x_i$ 必然和 $p ^ i$ 互质，所以 $x_i + Ip ^ i(p - 1)$ 和 $p ^ i$ 互质，故和 $p ^ {i + 1}$ 互质。欧拉定理可以用。

因为 $\varphi(p ^ {i + 1}) = p ^ i(p - 1)$，所以 $Ip ^ i(p - 1)\equiv 0\pmod {\varphi(p ^ {i + 1})}$，因此 $(x_i + Ip ^ i(p - 1)) ^ {x_i} \equiv D \pmod {p ^ {i + 1}}$。

这是一个 n 次剩余的形式。但是 $p ^ {i + 1}$ 太大，无法使用 BSGS 求解。

注意到 $Ip ^ i(p - 1)$ 的大于 $1$ 次方 $\bmod\ p ^ {i + 1}$ 等于 $0$，考虑 二项式展开。

$$(x_i + Ip ^ i(p - 1)) ^ {x_i} \equiv x_i ^ {x_i} + \dbinom{x_i} 1 x_i ^ {x_i - 1} \cdot Ip ^ i(p - 1) \equiv D \pmod {p ^ {i + 1}} $$

令 $v = x_i ^ {x_i}$，则 $vIp ^ i(p - 1)\equiv D - v\pmod {p ^ {i + 1}}$，即 $I\equiv \dfrac{D - v}{v p ^ i (p - 1)} \pmod {p ^ {i + 1}}$。

因为 $v \equiv D \pmod {p ^ i}$，所以 $D - v$ 是 $p ^ i$ 的倍数。设 $t = \dfrac {D - v}{p ^ i}$，则 $I \equiv \dfrac t {v(p - 1)} \pmod p$，显然 $v(p - 1) \perp p$，因此 $v(p - 1)$ 在模 $p$ 意义下的逆元存在，据此可求出 $I$。

注意到 $I < p$，因此 $I p ^ i (p - 1) < p ^ {i + 1}(p - 1)$，构造出的解远小于 $2 ^ {125}$ 这一上界，算法可行。

时间复杂度约为 $\mathcal{O}(T\log m\log n)$。

Sol 3

考虑 $n$ 是 square free number。

考虑 增量法构造。

设 $n$ 的质因子分别为 $p_1, p_2, \cdots, p_k$，令 $P_i = \prod\limits_{j = 1} ^ i p_j$，$Q_i = \prod\limits_{j = 1} ^ i (p_j - 1)$。

设 $x_i \equiv D \pmod {P_i}$，考虑如何从 $x_i$ 推到 $x_{i + 1}$。

如法炮制，发现令 $x_i \gets x_i + IP_iQ_i$ 仍然可行，因此设 $x_{i + 1} = x_i + IP_iQ_i$。但是再走二项式展开的老路就行不通了，因为 $P_iQ_i \not \equiv 0 \pmod {\varphi(P_{i + 1})}$。

怎么办呢？注意到若需保证 $x_{i + 1} ^ {x_{i + 1}} \equiv D \pmod {P_{i + 1}}$，因为必然有 $(x_i + IP_iQ_i) ^ {x_i + IP_iQ_i} \equiv D\pmod {P_i}$ 且 $P_i \perp p_{i + 1}$，根据中国剩余定理，只需保证 $(x_i + IP_iQ_i) ^ {x_i + IP_iQ_i} \equiv D\pmod {p_{i + 1}}$。发现还是很不好做，因为 $I$ 同时在底数和指数上，而且 $P_iQ_i \not \equiv 0 \pmod {p_{i + 1} - 1}$。

考虑化去指数上的 $I$。

尝试改变定义，令 $x_{i + 1} = x_i + IP_iQ_{i + 1}$，因为 $Q_{i + 1} \perp p_{i + 1}$，这为接下来寻找逆元奠定基础（如果令 $x_{i + 1} = x_i + IP_{i + 1}Q_{i + 1}$，实际上相当于给 $x_i$ 加上 $x_{i + 1}$ 的循环节 $\mathrm{lcm}(P_i, \varphi(P_i))$ 的倍数 $P_{i + 1}Q_{i + 1}$ 的倍数，显然不可行，因为当且仅当 $x_i$ 已经符合要求时我们能找到合法的 $x_{i + 1}$）且 $Q_{i + 1} \equiv 0 \pmod {p_{i + 1} - 1}$。

这样一来，上式化简为 $(x_i + IP_iQ_{i + 1}) ^ {x_i} \equiv D\pmod {p_{i + 1}}$。求解该 n 次剩余，令 $g$ 为 $p_{i + 1}$ 的任意原根，$g ^ u \equiv D\pmod {p_{i + 1}}$，则 $I \equiv \dfrac {g ^ {\frac u {x_i}} - x_i}{P_i Q_{i + 1}} \pmod {p_{i + 1}}$。

此时出现了一个严重的问题。分子的 $\dfrac u {x_i}$ 在模 $p_{i +1} - 1$ 意义下求解，但 $x_i$ 和 $p_{i + 1} - 1$ 可能不互质。

尝试修补这个问题。即尝试令 $x_i \perp p_{i + 1} - 1$。

接下来是一步巧妙转化：令 $x'_i \gets x_i + JP_iQ_i$，使得 $x_i + JP_iQ_i \perp p_{i + 1} - 1$。

但是又出现了问题，即 $P_iQ_i$ 可能和 $p_{i + 1} - 1$ 不互质。

给出引理：若 $a\perp d$，则对于任意 $n\geq 2$，存在 $J\in [0, n - 1]$ 使得 $a + Jd \perp n$。

证明：将 $n$ 分解质因数成 $\prod q_i ^ {c_i}$ 的形式。容易证明 $a \perp q_i ^ {c_i}$ 或 $a + d \perp q_i ^ {c_i}$。若非，说明 $a$ 和 $d$ 同时含有质因子 $q_i$，与假设矛盾。又因为若 $a + Jd \perp q_i ^ {c_i}$，显然 $a + (J + kq_i ^ {c_i})d \perp q_i ^ {c_i}$，即 $J$ 在 $q_i ^ {c_i}$ 模意义下。根据中国剩余定理，得证。

我们发现这是一个递归形式的问题，即若 归纳假设 $x_i \perp P_iQ_i$，则能找到这样的 $J$ 使得 $x_i + JP_iQ_i \perp p_{i + 1} - 1$，且上述引理给出了一个求解 $J$ 的方法，即对 $p_i - 1$ 分解质因数并 CRT 合并。而 若条件满足，则结论满足，推出下一轮的条件仍满足：$x'_i \perp p_{i + 1} - 1 \Rightarrow x'_i \perp P_iQ_{i + 1} \Rightarrow x'_i + IP_iQ_{i + 1} \perp P_iQ_{i + 1} \Rightarrow x_{i + 1}\perp P_iQ_{i + 1}$，又因为 $D\perp P_{i + 1}$，所以 $x_{i + 1} \perp P_{i + 1}Q_{i + 1}$。

同时，当在构造第一步时，Sol 2 满足归纳的初始条件，因为 $x_1 \equiv D \pmod {p_i}$ 且 $x_1 \equiv 1 \pmod {p_1 - 1}$，显然 $x_1\perp P_1Q_1$。

梳理一下上面的思路，发现添加限制 $x_i \perp P_iQ_i$ 之后，为了满足该性质所需进行的操作的正确性被该性质所保证，而一开始性质满足，故正确性得以保证。这是归纳法非常巧妙的应用。

这样，我们解决了 $\dfrac u {x_i}$ 可能无解的问题。

$P_iQ_{i + 1}$ 与 $p_{i + 1}$ 互质，其在模 $p_{i + 1}$ 意义下存在逆元。我们得以算出 $I \equiv \dfrac {g ^ {\frac u {x'_i}} - x'_i}{P_i Q_{i + 1}} \pmod {p_{i + 1}}$，从 $x_i$ 扩展至 $x_{i + 1}$。

时间复杂度约为 $\mathcal{O}(m ^ {\frac 5 4} + T\omega(n)(\log n + \sqrt m))$：预处理 $m$ 以内每个质数（约 $\frac m {\ln m}$ 个）的原根（单次复杂度 $m ^ {\frac 1 4} \log m$）。BSGS 求解离散对数方程时模数非常小，不需要 map 或哈希表，用数组记录即可。

由于 $I, J$ 均为 $p_{i + 1}$ 级别，因此对应的 $\sum IP_iQ_{i + 1}$ 和 $\sum JP_iQ_i$ 的一个粗略上界为 $\omega(n) n ^ 2$，略小于 $2 ^ {125}$ 的限制，符合要求。若担心超出上界，可以令 $x_i$ 对 $P_iQ_i$ 取模。

Sol 4

结合 Sol 2 和 Sol 3，从小到大考虑所有质因子。若相邻两个质因子相同，则使用 Sol 2，将对应的 $p ^ i (p - 1)$ 换成 $P_iQ_i$；否则使用 Sol 3 即可。

接下来是一些细节讨论：

• 在 Sol 2 使用欧拉定理时，需要 $IP_iQ_i \equiv 0 \pmod {\varphi(P_{i + 1})}$。考虑 $P_iQ_i$ 包含 $k$ 个质因子 $p_i$，则 $\varphi(P_{i + 1})$ 也包含 $k$ 个质因子（根据欧拉定理的计算式可得）。同时，$\varphi(P_{i + 1})$ 所有形如 $p_j - 1$ 的乘积项被 $Q_i$ 消去，因此上式仍然成立。
• 在 Sol 2 二项式展开时，需要 $IP_iQ_i$ 的大于 $1$ 次幂是 $P_{i + 1}$ 的倍数。显然成立，因为 $p_i = p_{i + 1}$。
• 在 Sol 2 求解 $I$ 时，需要 $\dfrac {D - v}{vP_iQ_i}$ 在模 $P_{i + 1}$ 意义下存在。由于分子，分母和模数均为 $P_i$ 的倍数，因此同除后分母 $vQ_i$ 和 $p_{i + 1}$ 互质，这是因为 $v$ 显然和 $p_i$ 互质，且 $p_{i + 1} = p_i$。
• 在 Sol 3 中的归纳假设需要在 Sol 2 中满足，因为我们会交替使用 Sol 2 和 Sol 3。因为 Sol 2 的初始条件成立，所以 $x_i \perp P_iQ_i$。因为 $P_{i + 1}Q_{i + 1}$ 相较于 $P_iQ_i$ 没有增加更多质因子，所以显然 $x_{i + 1}\perp P_{i + 1}Q_{i + 1}$。

综上，时间复杂度 $\mathcal{O}(m ^ {\frac 5 4} + T((\omega(n) + \log m)\log n + \omega(n) \sqrt m))$，常数较大。

可以获得 100 分的好成绩。

一些补充：

• 在求解 $J$ 时，可以每次给 $x_i$ 加上 $P_iQ_i$ 直到符合要求而非 CRT 求解。因为每次加上 $P_iQ_i$ 可以看做从 $0\sim p_{i + 1} - 1$ 中随机选一个数，期望随机 $\dfrac {p_{i + 1} - 1} {\varphi(p_{i + 1} - 1)} - 1$ 次（初始状态算一次）即可得到与 $p_{i + 1} - 1$ 互质的 $x_i + JP_iQ_i$。
• 笔者认为本题是一道不可多得的数论好题。尽管其形式简单，但却涉及到了 exgcd 求逆元，CRT 合并同余方程，BSGS 求解离散对数和 n 次剩余问题。归纳法用得恰到好处。整个算法优美而简洁，思维难度极高。没有冗余步骤，只是纯粹的数论。