这篇基本上都是抄的迟帅的博客@Mys_C_K 希望他不要介意/kel
数论函数的狄利克雷卷积可转化为贝尔级数的卷积
定义$f$模$p$的贝尔级数为
$f_p(x)=sum_{0leq i} f(p^i)x^i$
其实就是把原来的指数移到现在的下标
写几个常见的贝尔级数
$$
e_p(x)=1\1_p(x)=sum_{i geq 0} x^i =frac{1}{1-x}\id_p(x)=sum_{i geq 0} p^ix^i = frac{1}{1-px}\ mu_p(x)=1-x\ mu^2_p(x)=1+x\ (id cdot mu)_p(x)=1-px\ phi_p(x)= sum_{i geq 0} p^{i-1}(p-1)x^i = frac{1-x}{1-px}\ lambda_p(x) = sum_{i geq 0} (-1)^ix^i =frac{1}{1+x}
$$
具体的例子：
$frac{1}{1-px}(1-px)=1 ightarrow id * (mu cdot id) =e$
考虑求$mu^2*(id cdot mu)$ 发现他卷上$id(x)$是$mu^2$也就是现在如何求$mu ^2$显然可以直接莫反
好惹 我发现我并不会杜教筛x
好惹 我又会杜教筛惹
杜教筛长这样
$sum_{i=1}^n g(i) = S(n)$我们要求S
我们考虑这么做$ g(1)S(n) = sum_{i=1}^n(f*g)(i) - sum_{d=2}^ng(d)S(lfloor frac{n}{d} floor)$
我们只要找到能快速计算的$f*g$的前缀和于是递归下去求解就可以了