前置条件
分析
在从基础数论函数说起1：整除分块、数论函数、狄利克雷卷积的最后，提到了 (e=mu * 1) 。
也就是说，在狄利克雷卷积意义下， (mu) 和 (1) 互为逆元。
那么如果要求 (f(n)) ，而 (g(n)=sumlimits_{d|n}f(d)) 其中的 (g(n)) 能够非常方便地求出。可以看做 (g=f*1) 。两边同乘 (mu) ，得到 (f=mu * g) 。即
[g(n)=sumlimits_{d|n}f(d)\,\,Rightarrow\,\, f(n)=sumlimits_{d|n}mu(frac{n}{d}) g(d)
]
这被称为 因数反演 。
同样的，还有 倍数反演 。
[g(n)=sumlimits_{n|d} f(d) \,\,Rightarrow\,\, f(n)=sumlimits_{n|d} mu(frac{d}{n})g(d)
]
感觉不是很会正向推导。那就只能暴力证明一波了：
[sumlimits_{n|d}muleft(frac{n}{d}
ight)g(d)=sumlimits_{k}mu(k)g(nk)=sumlimits_{k}mu(k)left(sumlimits_{nk|t}f(t)
ight)=sumlimits_{t}f(t)left(sumlimits_{nk|t}mu(k)
ight)=sumlimits_{t}f(t)eleft(frac{t}{n}
ight)=f(n)
]
推荐题目
更多
既然提到了反演，那么还有另外两种反演值得一看。具体地以后再分析。
二项式反演
[f(n)=sumlimits_{i=0}^n {nchoose i}g(i)\,\,Rightarrow\,\, g(n)=sumlimits_{i=0}^n(-1)^{n-i}{nchoose i} f(i)
]
也可以写成
[f(n)=sumlimits_{i=0}^n (-1)^i {nchoose i}g(i) \,\,Rightarrow\,\, g(n)=sumlimits_{i=0}^n(-1)^i{nchoose i}f(i)
]
斯特林反演
[f(n)=sumlimits_{i=0}^nleft{egin{matrix}n\iend{matrix}
ight}g(i) \,\,Rightarrow\,\, g(n)=sumlimits_{i=0}^n(-1)^{n-i}left[egin{matrix}n\iend{matrix}
ight]f(i)
]