P8457 「SWTR-8」幂塔方程

· · 题解

P8457 「SWTR-8」幂塔方程

题目描述

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

他想让你求解：

x ^ x\equiv D \pmod n

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

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

多组测试数据。

数据范围

对于 100\% 的数据：

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} 可能无解的问题。

时间复杂度约为 $\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 次剩余问题。归纳法用得恰到好处。整个算法优美而简洁，思维难度极高。没有冗余步骤，只是纯粹的数论。