杜教筛

附：常见卷积式子
\(\epsilon=\mu*1\)
\(id=\phi*1\)
\(\phi=id*\mu\)
\(\sigma_0=1*1\)
\(\sigma_1=1*id\)
\(\sigma_2=id*id\)
\(f=f*\epsilon\)

就是利用狄利克雷卷积的性质。不算是个筛法。
\(\sum_{i=1}^n\epsilon(n)=\sum_{i=1}^n\sum_{d|i}\mu_d1(\frac i d)\)，
常见 trick：因数变倍数：
\(\sum_{i=1}^n\epsilon(n)=\sum_{d=1}^n 1(d) pre_{n/d}\)。
\(\sum_{i=1}^n\epsilon(n)=pre_n+\sum_{d=1,d\neq 1}^n pre_{n/d}\)
利用狄利克雷卷积搞递推式的性质即可。如果直接做可用微积分证明是 \(\mathcal {O}(n^{\frac 3 4})\) 的，如果筛出 \(n^\frac 2 3\) 的数，后面的再这样做，可做到 \(\mathcal {O}(n^\frac 2 3)\)。
关于 \(\phi_i\)：
\(\sum_{i=1}^nid_i=\sum_{i=1}^n\sum_{d|i}\phi_d 1(\frac i d)\)，
\(\sum_{i=1}^nid_i=pre_n+\sum_{i=2 }^n pre_{n/d}\)

现在来个非常见函数：求 \(\sum_{i=1}^n i*\phi_i\)
令 \(f_i=i*\phi_i\)，我们也试图找出其卷积式。考虑这个 \('i*'\) 看着很不爽啊，那就把它消掉。则由 \(\phi *1=id\) 容易发现 \(\sum_{i|n}i*\phi_i*\frac n i=id_n*n\)，则 \(f*id=id_2\)。
待续。