前言
咕咕了好久终于来学习莫反了要不是不让在机房谁会发现数学一本通上有这么神奇的东西
就是没有性质的证明
然后花了两节数学课证明了一遍
舒服~
前置知识:欧拉函数,二项式定理(组合数)
会欧拉函数的可以直接看\(Mobius\)了
欧拉函数
含义
\(\phi (n)\) 表示比\(n\)小的数中与\(n\)互质的数的个数
引理1
- \(n\)为质数,\(\phi(n) = n - 1\)
- \(n=a*b\) 且 \((a, b) = 1\),则\(\phi(n) = \phi(a) * \phi(b)\)
- 对于一个质数\(n\)的\(a\)次方 \(\phi(n^a) = (n - 1) * p^{n-1}\)
现对于第三条性质给出证明 - 比\(n^a\)小的数有\(n^a - 1\)个
- 其中能整除的表示为\(n* t (t = 1, 2, ... n ^{a-1}-1)\)
- 总计有\(n^{a-1}-1\)个数能被整除
- 则与其互质的数的个数为\(\phi(p^a) = (n^a-1) - (p^{a-1}+1) = p^a - p^{a-1} = (p-1) * p^{a-1}\)
引理2
对于质数\(n\),唯一分解定理 \(n = {p_1}^{c_1} * {p_2} ^{c_2}...{p_k}^{c_k}\)
$ \phi(n) = (1- \frac 1 {p_1}) * (1- \frac 1 {p_2}) ... (1- \frac 1 {p_k})\(**
**若\)a\(与\)m\(互质,\)a^{\phi(m)} \equiv 1 (mod ; m)$
线性筛
根据上述性质,推出
- 若\(p\)为质数,\(\phi (p) = p - 1\)
- \(if(i \% p == 0) \:\ \phi(i*p)=p*\phi(i)\)
- \(if(i \% p \; != 0) \:\ \phi(i*p)=\phi(i)*(p -1)\)
code
inline void pre(int n){
phi[1] = 1;
for(int i = 2; i <= n; i++){
if(!vis[i]){
prime[++cnt] = i;
phi[i] = i - 1;
}
for(int j = 1; j <= cnt && i * prime[j] <= n; j++){
vis[i * prime[j]] = 1;
if(i % prime[j] == 0){
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
}
莫比乌斯反演(Mobius)
定义
对于非负整数集合上的两个函数\(F(n)\)和\(f(n)\),若满足条件\(F(n)=\sum_{d|n}f(d)\)则
$$f(n)=\sum_{d|n}\mu(d)F(\frac n d)$$
\(\mu\)函数
定义如下
- 若\(d=1\)则\(\mu(d)=1\)
- 若\(d=p_1p_2p_3...p_k\)均为互异质数,则\(\mu(d)=(-1)^k\)
- 其他情况\(\mu(d)=0\)
性质一
\[ \sum_{d|n}\mu(d) = \begin{cases} 1, & \text n=1 \\ 0, & \text n>1 \end{cases} \]证明:
若\(n\)为质数,显然\(sum=0\)
若\(n\)为合数,根据唯一分解定理
\(n\)的因子\(d\)只能是\(p_1p_2,p_1p_3,p_3p_k\)诸如此类
可以发现\(d\)的构造来自于\(k\)个质因子中选取了\(i\)个
- k为奇数
从\(k\)中选出奇数个因子,\(\mu\)值为-1,对答案贡献为\(-\sum_{i-1}^kC_k^i(i+=2)\) - k为偶数