题解：CF2147G Modular Tetration

· · 题解

考虑刻画 a 的合法性。

定义函数 g：x=\prod_{i\in S} p_i^{\alpha_i}(p_i\in \text{Prime},\alpha_i>0)，则 g(x)=\prod_{i\in S}p_i。那么第二条限制可以改写为 g(\text{ord}_m(a))|a。

因为 \gcd(a,m)=1，有 \gcd(\text{ord}_m(a),m)=1。因此若固定 a\bmod m=t 的值，则随机选数满足条件的概率为 \dfrac{1}{g(\text{ord}_m(t))}。

即求 \dfrac{1}{m}\sum_{i=0}^{m-1}\dfrac{1}{\text{ord}_m(i)}。令 c(x)=\sum_{i=0}^{m-1}[\text{ord}_m(i)=x]，即求：\dfrac{1}{m}\sum_{\gcd(i,m)=1,i|\varphi(m)}\dfrac{c(i)}{g(i)}。只需要考虑 c 怎么算。

引理：若 $m=p^{\alpha}(p\in \text{Prime})$，则 $\forall x|\varphi(m),c'(x)=x$。 证明：记原根为 $g$，让 $i\to ig$ 连成一张图，则 $g$ 所在的就是一个环。则 $\text{ord}_m(g^k)=\dfrac{\varphi(m)}{\gcd(\varphi(m),k)}$，这个值为 $x$ 的因数可得： $$ \dfrac{\varphi(m)}{\gcd(\varphi(m),k)}|x \\ \dfrac{\varphi(m)}{x}|\gcd(\varphi(m),k)\\ \dfrac{\varphi(m)}{x}|k $$ 因此这样的 $k$ 有 $x$ 个。 根据质因子的独立性，同样有 $c'(x)=x$。 再枚举 $g(i)=x$，记 $p_i$ 的出现次数为令 $x$ 的质数集合为 $S$，则有 $\sum_{T\subseteq S}(\prod_{p_i\in T}p_i^{\alpha_i})(-1)^{|S|-|T|}=\prod_{i\in S}( p_i^{\alpha_i}-1)$。 综上，答案是 $\dfrac{1}{m}\prod_{i|\varphi(m),i\nmid m,i\in \text{Prime}}(1+\dfrac{p_i^{\alpha_i}-1}{p_i})$。前面的 $1$ 表示不选的贡献。 <https://codeforces.com/contest/2147/submission/346173729>。