容斥原理与欧拉函数，莫比乌斯函数-学习笔记
CJ_Fu
·
·
个人记录
容斥原理
容斥原理的一般性
设 |S| 表示集合 S 中数的个数。
则有：
\left|\bigcup_{i=1}^{n} S_{i}\right|=\sum_{m=1}^{n}(-1)^{m-1} \sum_{a_{i}<a_{i+1}}\left|\bigcap_{i=1}^{m} S_{a_i}\right|
容斥系数
组合恒等式：
\sum_{i=0}^n(-1)^i\binom{n}{i}=0
所以容斥系数是 ±1。
欧拉函数 (φ)
(bushi
令 $A_k$ 表示 $n$ 的第 $k$ 个质因子的倍数所构成的集合。
容斥得：
$$φ(n)=\left|\bigcap_{i=1}^k\overline{A_i}\right|=n\prod_{i=1}^k\left(1-\frac{1}{p_i}\right)$$
---
### 性质
- $φ(1)=1$；
- 对于质数 $p$， $φ(p)=p-1,φ(p^k)=p^k-p^{k-1}$；
- $\gcd(a,b)=1$ 时，$φ(ab)=φ(a)φ(b)$。
---
## 莫比乌斯函数 ($\mu$)
### 定义
$$\mu(n)=\left\{\begin{array}{cc}
1 & n=1 \\
(-1)^{k} & n=p_{1} p_{2} \cdots p_{k} \\
0 & \text { 其余情况 }
\end{array}\right.$$
---
### 性质
$$\sum_{d|n}\mu(d)=[n=1]$$
---
## 积性函数
$\varphi$ 和 $\mu$ 都是积性函数。
---
### 性质：
对于定义域在正整数的函数 $f(x)$，有如下性质：
- $f(1)=1$；
- $\gcd(a,b)=1$ 时 $f(ab)=f(a)f(b)$。
可用筛法快速求 $\varphi$ 和 $\mu$。
埃氏筛：
```cpp
for(int i=1;i<=n;i++)miu[i]=1,v[i]=1,phi[i]=i;
for(int i=2;i<=n;i++)if(v[i]){
p[++t]=i;miu[i]=-1;phi[i]=i-1;
for(int j=2;j<=n/i;j++){
int k=i*j;
v[k]=0;
phi[k]=phi[k]/i*(i-1);
if(j%i==0) miu[k]=0;//埃式筛筛质数表、求μ、求φ三合一
else miu[k]*=-1;
}
} //p[]为质数表,v[]为质数标记,miu[]为μ，phi[]为φ
```
线性筛：
```cpp
for(int i=1;i<=n;i++)miu[i]=1,v[i]=1,phi[i]=i;
for(int i=2;i<=n;i++){
if(v[i]){miu[i]=-1;phi[i]=i-1;p[++t]=i;}
for(int j=1;j<=t&&i*p[j]<=n;j++){
int k=i*p[j]; //线性筛筛质数表、求μ、求φ三合一
v[k]=0;
if(i%p[j]==0) {miu[j]=0;phi[k]=p[j]*phi[i];break;}
else {miu[j]*=-miu[i],phi[k]=(p[j]-1)*phi[i];}
}
}//p[]为质数表,v[]为质数标记,miu[]为μ, phi[]为φ
```