懵 逼 钨 丝
本文参考借鉴于知乎上$Syu Gau$与$阮行止$在$如何证明莫比乌斯反演?$这一问题下的回答.
前置知识
1.卷积
首先我们先设$f,g$为两个数论函数。
则卷积定义为$(f\times g)(n)=\sum_{ij=n}f(i)g(j)$。(注意本文的$\times$不是乘,是卷积运算,乘都已省略)
易证卷积满足交换律与结合律。
那么让我们设想一个单位元数论函数$\iota$,这个$\iota$满足$(a\times f)(n)=f(n)$
那就要满足$(f\times a)(n)=\sum_{ij=n}f(i)a(j)$
显然$a(n)=[n=1]$
让我们继续定义,通过狄利克雷卷积可知
对于$f,g$数论函数,还有一种卷积写法为$(f\times g)(n)=\sum_{d\mid n}f(d)g(n/d)$
用你的膝盖想一想,你会发现$(f\times g)(n)=\sum_{d\mid n}f(d)g(n/d)=\sum_{ij=n}f(i)g(j)$这两种写法完全等价。
OK,到此前置知识全部讲完,让我们开始证明莫比乌斯反演。
我们要证明当有$F(n)=\sum_{d\mid n}g(d)=\sum_{d\mid n}g(n/d)$时,$g(n)=\sum_{d\mid n}\mu(d)f(n/d)=\sum_{d\mid n}\mu(n/d)f(d)$
考虑转化为狄利克雷卷积,我们设一个函数$b$,它把所有数都映射成1.
则原问题被转化为已知$F=g\times b$。
求证$g=F\times \mu$
因为单位元函数的性质,任何函数卷上它都是自己本身,所以有$F\times a=g\times b$
因为莫比乌斯函数定义则$\mu\times b=a$
这个很好证$(\mu\times b)(n)=\sum_{d\mid n}\mu(d)$
而$\mu$函数有个性质就是$\sum_{d\mid n}\mu(d)=[n=1]$
所以上式成立(极不严谨)。
那么$F\times a=g\times b$
可化为$b\times F\times \mu=g\times b$
两边把$b$逆元一卷,完美消掉。
便证得$g=F\times \mu$
也就有$g(n)=\sum_{d\mid n}\mu(d)f(n/d)=\sum_{d/n}\mu(n/d)f(d)$
应用
P1829 [国家集训队]Crash的数字表格 / JZPTAB
就是求$\sum^{n}_{i=1}\sum^{m}_{j=1}lcm(i,j)$
显而易见是莫反题
$\sum^{n}_{i=1}\sum^{m}_{j=1}lcm(i,j)$.
可变为
$\sum^{min(n,m)}_{k=1}\sum^{n}_{i=1}\sum^{m}_{j=1}ij/k[gcd(i,j)=k]$.
然后变为
$\sum^{min(n,m)}_{k=1}\sum^{n/k}_{i=1}\sum^{m/k}_{j=1}ijk*[gcd(i,j)=1]$.
等于
$\sum^{min(n,m)}_{k=1}\sum^{n/k}_{i=1}\sum^{m/k}_{j=1}ijk*\sum_{d\mid gcd(i,j)}\mu(d)$.
上面又等于
$\sum^{min(n,m)}_{k=1}k\sum^{n/k}_{i=1}i\sum^{m/k}_{j=1}j\sum_{d\mid gcd(i,j)}\mu(d)$
然后枚举$d$
可得
$\sum^{min(n,m)}_{k=1}k\sum^{min(n/k,m/k)}_{d=1}\mu(d)d^2\sum^{n/kd}_{i=1}i\sum^{m/kd}_{j=1}j$
显而易见这个$\mu(d)d^2$是积性函数可以筛,这个自己推导下。
然后除法搞定。
代码
1 |
|
杜教筛
明天更新
代码
1 |
|