狄利克雷卷积
定义:\((f*g)(n)=\sum_{d|n}f(d)g(n/d)\)
很显然满足交换律和结合律。
积性函数
为积性函数的有:
\(I (n)\) (或\(1(n)\) ),恒等于1，所以叫恒等函数
\(\epsilon (n)\) (或者\(e(n)\) ),当且仅当 \(n=1\) 时，其值为 \(1\),否则为 \(0\),其满足(\(e*f=f\))(因此为狄利克雷卷积的单位元)
\(id(n)=n\) 为单位函数。
以上为完全积性函数。
完全积性函数:对于任意整数 \(a\) 和 \(b\) 满足 \(f(ab)=f(a)f(b)\)
以及：
\(\varphi (n)\) ,欧拉函数，小于 \(n\) 的整数中与 \(n\) 互质的数的个数。
\(\mu (n)\) ,莫比乌斯函数，接下来我们重点讲，暂且不介绍。
积性函数:对于两个整数 \(a,b\) ，满足 \((a,b)=1\) ，则 \(f(ab)=f(a)f(b)\)
虽然没有完全积性函数优美，但是这很好吧，这可以吧。(
然后研究一下这个积性函数的性质。
- 积性函数 \(f\),总满足 \(f(1)=1\)
这个易证了，\(f(1)=f(1)f(1)\)
- 两积性函数之积为积性函数。
这个稍微难一点。
证明:
定义两个积性函数 \(f,g\) ,其卷积为 \(G=f*g\).
任取两个互质的数 \(a,b\)
\(G(a)G(b)\)
\(=\sum_{d|a}f(d)g(b/d)*\sum_{t|b}f(t)g(b/t)\)
\(=\sum_{d|a}\sum_{t|b}f(d)g(a/d)f(t)g(b/t)\)
\(=\sum_{dt|ab}f(dt)g(ab/dt)\)
\(=G(ab)\)
\(Q.E.D.\)
- 积性函数的逆也是积性函数
归纳证明，就不证明了
莫比乌斯函数
引入
对于两个函数 \(f,F\),满足 \(F(n)=\sum_{d|n}(1*f(d) )\)
等价于 \(F=\Iota *f\),然后有 \(f=\Iota^{-1}*F\)
我们把 \(\Iota^{-1}\) 称为 \(\mu\) 莫比乌斯函数。
也就有 \(f=\mu *F\)
定义:
然后有个性质：
- \((\mu *1)=e\)
从定义出发易证。互逆的两个函数卷起来是单位元。
- \(\varphi *1=id\) ,然后 \(\varphi=\mu *id\)
由 \(\varphi *1=id\)，且 \(\mu *1=e\)
得 \(\varphi * 1 *\mu=id*\mu\) 即 \(\varphi=\mu *id\)
然后证一下 \(\varphi *1=id\)
想了解可以参考 OI wiki
莫比乌斯反演
进入正题。
- 嵌入式莫比乌斯反演
由 \(\mu *1=e\) 得 \(\sum_{d|n}\mu(d)=[n=1]\)
因为 \([n|m][n/m=1]=[n=m]\)
所以有 \([n|m]\sum_{d|(n/m)}\mu(d)=[n=m]\) (因为只有当n=1的时候这个玩意才满足)
可以这么转换。
- \(\sum_{d|(i,j)}\mu (d)=[(i,j)=1]\)
因为 \(\sum_{d|(i,j)}\mu (d)=e(gcd(i,j) )\),易证
然后你肯定是要会算莫比乌斯函数的，开筛！
这个我们之前的博客中有，于是不多说了。筛
变换形式
- \(F(n)=\sum_{d|n}f(d) \Leftrightarrow f(n)=\sum_{d|n}\mu(d)F(n/d)\)
本质还是
\(F=1*f \Leftrightarrow f=F*I^{-1} \Leftrightarrow f=F*\mu\)
数论分块
用来计算形如 \(\sum_{i=1}^{n}f(i)g(\lfloor \frac{n}{i} \rfloor)\) 的和式。
我们再单独来讲这个 数论分块
我们推个式子：
\(ans=\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=1]\)
\(=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|(i,j)}\mu(d)\)
\(=\sum_{d=1}^{min\{n,m\}}\mu(d)\sum_{d|i}^{n}\sum_{d|j}^{m}1\)
\(=\sum_{d=1}^{min\{n,m\}}\mu(d)\lfloor n/d \rfloor \lfloor m/d \rfloor\)
这个式子我们可以 \(O(n)\) 的算。
接下来我们用数论分块处理，达到 \(O(\sqrt{n})\)
总之莫反的题就是分为反演和分块，学懂了还是挺套路的。