\(n=\prod_{i=1}^k p_i^{a_i}\)，设函数\(f_d(x)=\prod_{i=1}^k(-1)^{a_i}[a_i\leq d]\)，求\(\sum\limits_{i=1}^nf_d(i)\)。
真是反套路，和平常思路完全不同的凑杜教筛法
用贝尔级数凑杜教筛的话，发现这东西形式非常不好看，主要是因为他项比较多，还不是无限项没有较简单的封闭形式。
那就考虑用表达式类似，形式很好看的\(\lambda\)来容斥他。这个\(f_d(x)\)和\(\mu\)有点像，他的意思就是不存在幂次为\(d+1\)的因数，那就用这个来容斥
就是枚举他有哪些幂次\(d+1\)的因子，容斥系数恰好为\(\mu(i)\)。把这个代入前缀和得
发现\(j\)的枚举量至多是\(O(\sqrt n)\)，暴力枚举即可。现在问题就在如何快速求\(\lambda(i)\)的前缀和。
他的贝尔级数为\(\frac{1}{1+x}\)，正常还以为要和贝尔级数为\(1+x\)的\(\mu^2\)卷。
其实也行，对于每个\(x=\lfloor \frac{n}{i} \rfloor\)位置可以\(O(\sqrt x)\)求出\(\mu^2\)前缀和，积分可得复杂度也是\(O(n^{\frac{3}{4}})\)。用杜教筛常用优化预处理，也可以做到\(O(n^{\frac{2}{3}})\)。
其实有更简单的凑法。就是考虑\(1\)函数的贝尔级数为\(\frac{1}{1-x}\)，他俩卷得\(\frac{1}{1-x^2}\)。
展开这个封闭形式就是\(f_p(x)=\sum\limits_{i\geq 0}x^{2i}\)，可以发现这个函数就是\(f(x)=[x为完全平方数]\)。这样可以直接杜教筛了。
原文：https://www.cnblogs.com/LebronDurant/p/14905085.html