题解：CF2147G Modular Tetration

由于 $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$。分母是固定的，分子可以乘法分配律直接计算。

$m$ 和 $\varphi(m)$ 的质因数分解可以依靠预处理 $\le 10^6$ 的数的最小质因子计算，因为可能需要给质因子去重，时间复杂度为 $O(m^{1/3}+T\log m\log\log m)$。

code。