数论
light_searcher
·
·
个人记录
欧拉函数
欧拉函数 \varphi(n) 为 1 \sim n-1 中与 n 互质的数的个数。
欧拉函数的性质：
- 若 p 为质数，则 \varphi(p)=p-1
- 若 p 为质数，k 为正整数，则 \varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)
- 若 a,b 互质，则 \varphi(ab)= \varphi(a)\varphi(b)，即欧拉函数是积性函数
欧拉函数的计算公式： \varphi(n) = n \prod\limits_{i=1}^s \frac{p_i-1}{p_i}
证明：设 n=\prod\limits_{i=1}^s p_i^{k_i}，其中 p_i 为质数且互不相同，则 p_i^{k_i} 互质，由性质 3 可得 \varphi(n)=\prod\limits_{i=1}^s\varphi(p_i^{k_i})。
再由性质 2 可得 \varphi(n)= \prod\limits_{i=1}^sp_i^{k_i-1}(p_i-1)=\prod\limits_{i=1}^sp_i^{k_i} \frac{p_i-1}{p_i}= n \prod\limits_{i=1}^s \frac{p_i-1}{p_i}。
卷积
狄利克雷卷积：\sum \limits_{d \mid n} f(d)g(\frac{n}{d}).
$\sum \limits_{d \mid n} \mu(d)=[n=1] \iff \mu *1=\varepsilon$.
$\sum \limits_{d \mid n} \mu(d) \frac{n}{d}=\varphi(n) \iff \mu *id= \varphi$.
## 莫比乌斯反演
### 筛法莫比乌斯函数
```cpp
mu[1]=1;
for(int i=2;i<=n;i++){
if(isprime[i]){
prime.push_back(i);
mu[i]=-1;
}
for(int j=0;j<prime.size()&&i*prime[j]<=n;j++){
isprime[i*prime[j]]=0;
if(!(i%prime[j])){
mu[i*prime[j]]=0;
break;
}
mu[i*prime[j]]=-mu[i];
}
}
```
### 定义
$f(n)=\sum\limits_{d|n} g(d) \iff g(n)=\sum\limits_{d \mid n} \mu(d) f(\frac{n}{d})$.
证明：
- 若 $f=g*1$，则 $ \mu * f=\mu *g*1=g* \mu *1 = g*\varepsilon =g$.
- 若 $\mu *f=g$，则 $g*1=f*\mu * 1= \mu *1*f=f* \varepsilon =f$.