2023 牛客多校 9 B

给定 \(1 \le a < m \le 10^9\)，求 \(1 \le u \le 10^{18}\) 使得 \(a^u \equiv u \pmod m\)。

做法

先考虑不限制解的大小怎么做。显然有如果 \(a^v \equiv v \pmod {\varphi(m)}\)，且 \(v \ge \varphi(m)\)，则 \(a^{a^v} \equiv a^v \pmod m\)，于是取 \(u = a^v + m\varphi(m)\) 是一组当前问题的解，且 \(u \ge m\)。又有一个数迭代取 \(\varphi\)，只需要 \(\log\) 次就变成 \(1\)，由此得到一个递推做法。在限制解的大小的前提下，发现可以对 \(m\varphi(m)\) 取模，于是解变为 \(a^v \bmod (m\varphi(m)) + m\varphi(m)\)，不好的是这个数可能达到 \(2m\varphi(m)\) 级别，大于了 \(10^{18}\)，但是考虑最后一轮其实不一定需要加上 \(m\varphi(m)\)，因为没有下一次迭代。唯一的例外是如果 \(a^v \bmod (m\varphi(m)) < \varphi(m)\) 时必须加上，此时容易发现解不会超过 \(10^{18}\)。