这一篇( exttt{blog})应该算这篇的后续，所以可以先看一下这一篇QwQ
0. 一些奇奇怪怪的数论函数
(egin{aligned}1. ; & extbf{1}(x) = 1 \2. ; & extbf{id}(x) = x, extbf{id}^k(x) = x ^ k \3. ; & extbf{d}(x) = sum_{d mid x} 1 \4. ; & sigma(x) = sum_{dmid x} d\ 5. ; & epsilon(x) = [x = 1]end{aligned})
1. 狄利克雷卷积
若( extbf{h} = extbf{f} * extbf{g})，那么：
到这里我们可以推出一些奇奇怪怪的数论函数关系式：
(egin{aligned}1.;& extbf{d} = extbf 1 * extbf 1\ 2.; & sigma = extbf 1 * extbf{id} \ 3. ; & extbf{id} = extbf 1 * varphi \ 4. ; & sigma = extbf 1 * extbf 1 * varphi = extbf d * varphi end{aligned})
其中第四个是乱搞的（逃
2. 莫比乌斯反演
设(mu * extbf 1 = epsilon)，那么设( extbf f = extbf 1 * extbf g)，则( extbf g = mu * extbf f)
然后没了
到这里我们又可以推出一些奇奇怪怪的数论函数关系式：
(egin{aligned} 1. ; & varphi = extbf{id} * mu \ 2. ; & extbf 1 = mu * extbf d \ 3. ; & extbf{id} = sigma * mu end{aligned})
后面两个都是乱搞的（逃
说不定后面两个在杜教筛( extbf d)和(sigma)的时候有用（雾
前人研究了一下(mu)，发现这不仅牵涉到数论函数的关系，还发现它是一种特殊的容斥系数。这个特性等下再讲，先看一看(mu)的其它的性质。
我们研究一下(mu)在(p^k)处的取值（(p)是质数）
于是就可以非常好的线性筛了。
至于(mu)如何用容斥的方法理解，不想写了可以看yyb的博客
做题？题目一般会给出求(sum_{i=1}^nsum_{j=1}^m extbf f(gcd(i, j)))
然后套路就是可以变成(sum_{i=1}^n sum_{j=1}^m sum_{d | i, d | j} extbf g(d), extbf g = extbf f * mu)
接下来提出(d)就可以乱搞了。
给道例题，就写一道之前那篇文章写的有一点不完全的题目吧。
给定(n, m, (n leq m))求(sum_{i=1}^nsum_{j=1}^m sigma(gcd(i, j)))
(ecause extbf f = sigma, herefore extbf g = mu * sigma)
之前的g就止步于此
通过这篇文章的推导，我们翻上面的式子发现(mu * sigma = extbf{id})，于是( extbf g = extbf{id})
Wow!
那么可以推出：
写个鬼的线性筛，直接算不就可以了QwQ
3. 杜教筛
用来求积性函数前缀和。即求( extbf S(n) = sum_{i=1}^n extbf f(i))
假设我们找到了一个有趣的函数( extbf g)，使得( extbf g)和( extbf f * extbf g)的前缀和都可以快速求，那么我们可以快速求解( extbf S(n))了
那么( extbf g(1) extbf S(n) = sum_{i=1}^n ( extbf f * extbf g)(i) - sum_{i=2}^n extbf g(i) extbf Sleft(leftlfloorfrac ni ight floor ight))
前一半可以快速求，后一半可以数论分块(+)递归求。
复杂度？(mathrm{O}(n ^ {frac 23}))或者(mathrm{O}(n ^ frac 34))，这取决于你的实现方式。
然后对于(sum_{i=1}^n ( extbf f * extbf g)(i))要多快速求呢？首先如果可以(mathrm{O}(1))算是坠好的，然后我们发现后面要(mathrm{O}(sqrt n))的计算，所以这个柿子在(mathrm{O}(sqrt n))的时间复杂度内解决也是没有问题的。
同时这个玩意每次算的值都是一个(leftlfloorfrac nx ight floor)，所以求(sum_{i=1}^n ( extbf f * extbf g)(i))可以套一个杜教筛。
同理(sum_{i=1}^n extbf g(i))也可以套一层杜教筛，复杂度不会改变。
杜教筛的套路和莫比乌斯反演很像，都需要对狄利克雷卷积有深刻的理解和熟练的背诵。
莫比乌斯反演需要找到一个函数( extbf g = extbf f * mu)，杜教筛则是需要找到一个函数( extbf g)使得(sum extbf g(i))和(sum ( extbf f * extbf g)(i))可以快速计算。
所以上面的那些奇奇怪怪的数论函数关系式要记住。
举个例子吧，求(sum_{i=1}^n varphi(i))
找到一个函数( extbf g)使得(varphi * extbf g)可以快速算。
这个时候我们翻一下上面的式子可以发现(varphi * extbf 1 = extbf{id})，然后(sum extbf{id}(i))可以快速求，于是就做完了。
蛤？你说这个例子太简单？那就用一道题目来仔细讲一下这个套路吧。
洛谷P4213 【模板】杜教筛（Sum）
简单写一下题面，求：
化式子（这里如果有没看懂的，赶快回去复习一下）：
其中(S(x) = sum_{i=1}^x i)。
然后根据之前的套路，我们数论分块，问题转化为如何快速求(d^2varphi(d))的前缀和。
首先通过之前杜教筛可以再套杜教筛的理论，这里即使有一个数论分块，复杂度还是(mathrm{O}(n^frac 23))，于是复杂度是对的，可以放心筛。
接下来考虑对于( extbf f(x) = x^2varphi(x))，怎么找到一个合适的函数( extbf g)使得( extbf f * extbf g)好算。
定义点积(( extbf fcdot extbf g)(i) = extbf f(i) extbf g(i))，那么我们可以得到一个定理：
若( extbf f)为完全积性函数，( extbf g, extbf h)是数论函数，那么(( extbf f cdot extbf g) * ( extbf f cdot extbf h) = extbf f cdot( extbf g * extbf h))
证明的话显然。这个定理不就是给我们做题用的吗（逃
于是对于( extbf f = extbf{id}^2 cdot varphi)，可以找到( extbf g = extbf{id}^2 cdot extbf 1)，那么( extbf f * extbf g = extbf{id}^3, extbf g = extbf{id}^2)
然后就做完了。
接下来还有贝尔级数等一些鬼畜的高级玩意，直接给链接算了。