1.莫比乌斯函数与莫比乌斯反演
O.约定
\(\color{white}\colorbox{red}{本blog中所有的分数，无论有无下取整符号，均默认下取整。}\)
主要是因为我太懒了，下取整符号的\(\LaTeX\)表达式太长了
I.作用
设有一函数\(g(n)=\sum\limits_{d|n}f(d)\)。
显然，如果我们知道每个\(f(d)\)的值，那么\(g(n)\)的值应该是很容易得到的废话，不就按照定义瞎递推一下吗
那么如果我们知道每个\(g(n)\)的值，又应该如何求出\(f(d)\)来呢？
II.定义
我们引出莫比乌斯函数\(\mu(x)\)。
定义：
设\(x\)可以被质因数分解成\(\prod\limits_{i=1}^n(a_i)^{p_i}\)，则
\(\boxed{\mu(x)=\begin{cases}0(\exists i\in[1,n],p_i>1)\\(-1)^n(\forall i \in[1,n],p_i=1)\end{cases}}\)
换句话说，如果这个\(x\)包含某一个质数的平方或更高次数项，则\(\mu(x)=0\)；否则，如果它包含偶数个质因数，\(\mu(x)=1\)；否则，即它包含奇数个质因数，\(\mu(x)=-1\)。
这个形式诡异的函数有什么用吗？
III.性质
1.\(\mu(x)\)是积性函数。即，
\(\boxed{\forall \gcd(i,j)=1,\mu(i*j)=\mu(i)*\mu(j)}\)
因此，我们可以采用欧拉筛线性求它。
就是按照它的定义来求，因为积性函数都可以在线性筛时顺便求出。
int mu[N],pri[N];
void getmu(int n){
mu[1]=1;
for(int i=2;i<=n;i++){
if(!pri[i])pri[++pri[0]]=i,mu[i]=-1;
for(int j=1;i*pri[j]<=n&&j<=pri[0];j++){
pri[i*pri[j]]=true;
if(!(i%pri[j]))break;
mu[i*pri[j]]=-mu[i];
}
}
}
2.（最重要）
\(\boxed{\sum\limits_{d|x}\mu(d)=\begin{cases}1(x=1)\\0(x\neq1)\end{cases}}\)
证：
当\(x=1\)时，由定义，显然成立。
否则，设\(x=\prod\limits_{i=1}^n(a_i)^{p_i}\)。
对于它的每一个因数\(d\)，只有当\(d=\prod\limits_{i=1}^n(a_i)^{p_i},p_i\in\{0,1\}\)时，才有\(\mu(d)\neq 0\)。
如果\(d\)包含\(m\)个质因数，则\(\mu(d)=(-1)^m\)。在所有\(x\)的因数中，共有\(C_n^m\)个这样的\(d\)。
也就是说，\(\sum\limits_{d|x}\mu(d)=\sum\limits_{m=0}^n(-1)^mC_n^m\)
依据某奇妙的二项式定理，这个东西有\(\sum\limits_{m=0}^n(-1)^mC_n^m=(1-1)^n=0\)。
证毕。
IV.反演
正片开始。
回到我们一开始的说法。莫比乌斯反演对于\(g(n)=\sum\limits_{d|n}f(d)\)的函数\(f\)和\(g\)，假使我们知道每个\(g(n)\)的值，我们就可以反推出\(f(d)\)的值。
反演定理I：
\(\boxed{\text{如果}g(n)=\sum\limits_{d|n}f(d), \text{那么}f(x)=\sum\limits_{d|n}g(d)\mu(\dfrac{n}{d})}\)
证：
如果\(f(x)=\sum\limits_{d|n}g(d)\mu(\dfrac{n}{d})\)，
则一定有\(f(x)=\sum\limits_{d|n}g(\dfrac{n}{d})\mu(d)\)
在\(\sum\limits_{d|n}g(\dfrac{n}{d})\mu(d)\)中代入\(g(x)\)的定义\(g(x)=\sum\limits_{d|n}f(d)\)，
得\(\sum\limits_{d|n}g(\dfrac{n}{d})\mu(d)=\sum\limits_{d|n}(\sum\limits_{i|\frac{n}{d}}f(i))\mu(d)=\sum\limits_{d|n}(\sum\limits_{i*d|n}f(i))\mu(d)\)
我们将\(\mu(d)\)乘进括号，得
\(\sum\limits_{d|n}g(\dfrac{n}{d})\mu(d)=\sum\limits_{d|n}(\sum\limits_{i*d|n}f(i)\mu(d))\)
然后发现这个实际上的意思就是枚举所有的\(i\)和\(d\)，求\(f(i)\mu(d)\)的和。
因此有\(\sum\limits_{d|n}g(\dfrac{n}{d})\mu(d)=\sum\limits_{i|n}(\sum\limits_{i*d|n}f(i)\mu(d))=\sum\limits_{i|n}f(i)(\sum\limits_{i*d|n}\mu(d))\)
看一下后面的\(\sum\limits_{i*d|n}\mu(d)\)，有\(\sum\limits_{i*d|n}\mu(d)=\sum\limits_{d|\frac{n}{i}}\mu(d)\)。
是不是很熟悉？当\(\frac{n}{i}=1\)，即\(i=n\)时，该式值为\(1\)；否则，值为\(0\)。
则\(\sum\limits_{i|n}f(i)(\sum\limits_{i*d|n}\mu(d))=f(n)\)。因为\(i\neq n\)时后面的东西都是\(0\)。
证毕。
反演定理II：
\(\boxed{\text{如果}g(n)=\sum\limits_{n|d}f(d),\text{那么}f(x)=\sum\limits_{n|d}g(d)\mu(\dfrac{d}{n})}\)。
证法类似，也是把\(g(d)\)暴力代回去得证。留给读者自证。