luogu4240毒瘤之神的考验

题目描述

思路还是非常巧妙的。

看到$ij$粘在一起 所以考虑把$\phi(ij)$这个东西拆开。 考虑如下式子

考虑$\phi$的定义 $\phi(i)\phi(j)$ 相对于$\phi(ij)$来说 , 中间重叠了相同的一部分质因子$p_i$ 考虑除去这些质因子

可以除一下$\phi(gcd(i,j))$ 重叠的质因子是属于$gcd(i,j)$的 但是除掉$\phi(gcd(i,j))$以后 $ij $ 也被多除掉了$gcd(i,j)$,

所以考虑再把$gcd(i,j)$乘回来。 得到上式。

此时得到 式子

我们习惯性的把$gcd$提出来。得到

再把后面除掉$d$

来一发莫反

把枚举$\phi(id)\phi(jd)$作为系数 对每个$e$造成影响的是$e$在上界为$\frac{n}{d}$范围内的$d$的倍数。

接着枚举$de$的乘积$T$ 然后$\frac{d}{\phi(d)}$和$\mu(e)$脱成了卷积。

其中$G$可以调和级数复杂度处理出来 丢到一个$vector$里, $f$也可以调和级数复杂度处理。

其中