题解

显然有 \(ans=\sum _{i=1} ^{n} \lfloor \frac{n}{i} \rfloor \sum _{d|i} \mu(d) \phi (\frac{i}{d})\)

前半部分就是个整除分块，后半部分直接让脑子受到了冲击。

但是，我们知道，两个积性函数的\(\text{Direchlet}\)卷积还是积性函数，我们考虑构造线性筛。

我们看到其中有\(\text{Mobius}\)函数，鲁迅曾经说过“一看到\(\mu\)，就想到积性函数，就想到唯一分解，就想到\(>2\)的幂的贡献不计，就想到线性筛，\(\text{OIer}\)只有在这个方面思想如此跃进。”

我们尝试对一个数\(T\)因数分解。

设\(h(x)=\sum _{d|x} \mu(d) \phi (\frac{i}{d})\)对于其中一个素因子\(p\)和他的出现次数\(q\)，\(x=p^q\)我们发现

\(h(x)=1,q=0\)

\(h(x)=p-2,q=1\)

\(h(x)=p^{q-2}(p-1)^2,q>=2\)

显然$h(T)=\prod _{i=1}^{t} h(p_i^{q_i}) $我们根据这个构造线性筛

#include
    
     typedef long long ll;const int maxn = 1e7+10;ll h[maxn];int prime[maxn],cnt,n;bool vis[maxn];inline void prelude() {    h[1]=1;    for(int i = 2;i