题解：CF2147G Modular Tetration

diqiuyi · 2025-09-22 23:34:16 · 题解

由于 a^{a^{a^\cdots}}\equiv 1\pmod m，考虑 a 在模 m 意义下的阶 \delta_m(a)，它显然是 \varphi(m) 的因数。设 \varphi(m)=\prod_{i=1}^np_i^{\alpha_i}，记 f(S)=\prod_{i\in S}p_i^{\alpha_i},g(S)=\prod_{i\in S}p_i，则 \gcd(\varphi(m),a^{a^{a^\cdots}})\in\bigcup_S f(S)。

考虑枚举 S，显然 S 不能包含 m 的质因子。那么现在对于 a 的限制为 a^{f(S)}\equiv 1\pmod m,g(S)\mid a，以及 \gcd(a,m\frac{\varphi(m)}{f(S)})=1。由于这些限制都可以看作是独立的，这个概率可以写成 \dfrac{\frac{f(S)}{g(S)}\prod_{p_i\mid \varphi(m),i\notin S}\frac{p-1}p}m。分母是固定的，分子可以乘法分配律直接计算。