CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
=====比赛=====

无

=====学习总结=====


==== 莫比乌斯反演 ====

莫比乌斯反演：$g(n)=\sum_{d|n}f(d)$，则$f(n)=\mu *g$

$\epsilon(i)=[i=1]$在积性函数里扮演了类似于自然数中$1$的角色，为什么让$\epsilon$扮演自然数中$1$的角色呢，因为$(f*\epsilon)(n)=\sum_{d|n}f(\frac nd)\epsilon(d)=f(n)$。

$$id(i)=i$$

$$1(i)=1$$

$$\phi(i)=\text{多少个<i且与i互质}$$

$$d(i)=i \text{约数个数}$$

$$\sigma(i)=i \text{约数个数和}$$

设$n=\sum_{i=1}^{m}p_i^{k_i}$，则

$$\mu(n)=\left\{\begin{aligned}&1,&n=1\\&(-1)^m,&\forall _ik_i=1\\&0,&\exists_ik_i\geq2 \end{aligned}\right.$$

狄利克雷卷积中，$1$的逆是$\mu$，即$1*\mu=\epsilon$。

这很容易理解：对$(1*\mu)(n)$作出贡献的仅有**$n$的质因数的乘积**和**$1$**。

对于$n$的质因数，如果$n$有$m\geq 1$个质因数，那它就有$m$个“一个质因数的积”，$C_{m}^{2}$个“两个质因数的积，…，他们卷起来的和是

$$C_m^1+(-1)\cdot C_m^2+(-1)^2\cdot C_m^3+...+(-1)^mC_m^{m}=(1+(-1))^m-1$$

加上$1$的贡献，即为$0$。

所以只有当$n=1$的时候$(1*\mu)(n)$才为$1$，故$1*\mu=\epsilon$。

通过这个我们很容易推出莫比乌斯反演：$g=f*1$，所以$f=g*\mu$。

然后就是一些常见的结论：

$d=1*1$（枚举约数，对$1$求和）

$\sigma=d*1$（枚举约数，对约数求和）

$id=1*\phi$（枚举约数，每个约数求出小于他且与他互质的个数，即求这个约数为分母的真分数个数，它们的和必为$n$，例子见下：

$\frac 1{12}\frac 2{12}\frac 3{12}\frac 4{12}\frac 5{12}\frac 6{12}\frac 7{12}\frac 8{12}\frac 9{12}\frac {10}{12}\frac {11}{12}\frac {12}{12}$

可以化简为

$\frac 1{12},\frac 5{12},\frac 7{12},\frac{11}{12}$（$\phi(12)=4$）

$\frac 1{6},\frac 5{6}$（$\phi(6)=2$）

$\frac 1{4},\frac 3{4}$（$\phi(4)=2$）

$\frac 1{3},\frac{2}{3}$（$\phi(3)=2$）

$\frac 12$（$\phi(2)=1$）

$\frac 11$（$\phi(1)=1$）

根据$id=1*\phi$，有$\phi=id*\mu$

题目略（摸了，下次再补）

常用套路：$\sum_{i}\sum_{j}f(i,j)$变换为$\sum_{k}\sum_{i}\sum_{j}[f(i,j)=k]$这样拆出来，比如$f(i,j)=\gcd(i,j)$的时候拆出来比较容易进行反演之类的操作。

==== 组合数学 ====

需要注意的一个式子：$\sum_{i=L}^{R}C_{i}^{x}=C_{R+1}^{x+1}-C_L^{x+1}$。其实就是对$C_i^x=C_{i+1}^{x+1}-C_{i}^{x+1}$求和。
CVBB ACM Team

用户工具

站点工具

页面工具
