「FJWC2020Day5-zzq」lg

设模数为 \(P\)

考虑对于每一个 \(\gcd\) 计算 \(\text{lcm}\) 之积 \(F(m)\)

那么可以想到强制每个数都是 \(\gcd\) 的倍数，问题转化为求 \(\lfloor \frac{m}{gcd}\rfloor\) 以内所有 \(\text{lcm}\) 的积 \(G(m)\)

那么对于每个质因数依次考虑,则得到一个简单的式子

\[G(m)=\begin{aligned}\prod p_i^{\sum_{j=1}m^n-(m-\lfloor \frac{m}{p_i^j}\rfloor )^n} \end{aligned}\]

其中枚举的 \(j\) 是 \(p_i\) 至少出现 \(j\) 次的方案数，枚举的 \(j\) 是 \(\log m\) 级别的

肯定是先求出指数 \(\mod \varphi(P)\) ，可以线性预处理出所有的 \(i^n \mod \varphi(P)\)

对于每个 \(p_i\) 求出指数后还要快速幂，复杂度就是 \(O(|p_i|\log P)=O(m)\) ，实际带有一些常数

那么求 \(G(m)\) 的复杂度上界是 \(O(m\log m)\) ，实际上 \(\lfloor \frac{m}{i}\rfloor\) 有很多重复，复杂度要低很多

得到的每个 \(\gcd\) 的答案还要把强制取出的 \(\gcd\) 补上，是 $^