容斥原理
1.容斥原理
容斥原理用来解决求解\(|\bigcup_{i=1}^{n}A_i|\)的问题.
具体的,定义\(U=\{i|i\in \mathbb{Z},i\in[1,n]\}\),我们有公式:
\[|\bigcup_{i=1}^{n}A_i|=\sum_{S\in U}(-1)^{ |S| + 1}|\bigcap_{i\in S}A_i| \]由公式形式也不难观察到容斥原理可以化并为交.
2.欧拉函数
欧拉函数\(\varphi(n)=\#|\{x|x \perp n\}|\),若\(n=\prod_{i=1}^np_i^{k_i}\),则小于等于\(n\)中与\(n\)不互质的数是\(p_1\)或\(p_2\)...或\(p_n\)的倍数,为统计倍数的数量,设\(f(i)=\lfloor \frac{n}{i} \rfloor\),由于是"或"的关系,我们考虑化并为交.更具体的,举个例子,求\(\varphi(12)\),则为\(2\)或\(3\)的倍数,根据容斥原理则为\(f(2) + f(3) - f(6)\).为了确定符号,我们引入莫比乌斯函数\(\mu(x)\),其定义为:
\[\mu(x)= \begin{cases} 1 \ \ x = 1\\ 0 \ \ \text{x含有平方因子} \\ (-1)^k \ \ \text{k为x中本质不同的质因子数量} \end{cases} \]当我们发现容斥式子中所有的\(f(i)\)中\(i\)均不含平方因子,即这个\(i\)对答案并没有贡献,系数为零,因此:
\[n-\varphi(n)=\sum_{d | n}-\mu(d)f(d) = -n \sum_{d | n}\mu(d)\frac{1}{d} \]\[\varphi(n) = n(1+\sum_{d | n}\mu(d)\frac{1}{d}) \]我们考虑这个式子如何化简,我们发现\(d\)含有平方因子时对答案没有贡献,因此若\(n=\prod_{i=1}^kp_i^{k_i}\),则\(d=\prod_{i=1}^kp_i^{m_i},m_i\in\{0,1\}\),而此时由于\(\mu(d)\)当\(d\)中含有偶数个质数时为\(1\),奇数个质数时为\(-1\),那么我们发现这个系数分布与\(\prod_{i=1}^k(1-\frac{1}{p_i})\)是一致的----枚举每一个可能的质数乘积,偶数质数为正,奇数质数为负,甚至连\(+1\)都一模一样,因此我们有结论:
\[\varphi(n) = n(1+\sum_{d | n}\mu(d)\frac{1}{d}) = n\prod_{i=1}^k(1-\frac{1}{p_i}) \]至此,我们推出了欧拉函数的定义式.
3.莫比乌斯反演
我们研究上文所提到的\(\mu(x)\)的性质,发现当\(x > 1\)时有:
\[\sum_{d|x}\mu(d) = 0 \]如何证明呢?根据上文欧拉函数定义式的证明,我们已经深刻认识到了\(\mu(x)\)所对应的容斥原理系数的性质----奇数为负,偶数为负.因此我们尝试构造上述求和式有实际意义的场景.我们假设每个质数\(p_i\)对应一个集合\(A_i\),而对于一个合数\(n=\prod_{i=1}^kp_i^{k_i}\),\(A_n=\bigcap_{i=1}^kA_i\).我们发现在容斥原理公式中,奇数个质数系数应为\(1\),而偶数个质数的乘积应为\(-1\),这与\(\varphi(x)\)是相反的.因此根据容斥原理,\(|\bigcup_{i=1}^kA_i|\)可用如下式子表示:
\[-\sum_{d|x}\varphi(d)|A_d| \]但上面的式子有一个问题:我们在容斥求并集时,并没有定义\(A_1\),因此我们应该将额外的\(-\varphi(1)\)加回来.
综上所述,我们有公式
\[|\bigcup_{i=1}^kA_i|= \varphi(1)-\sum_{d|x}\varphi(d)|A_d| \]这时,我们发现离目标已经不远了,我们只需要构造\(A_i\)即可,我们发现,只要让所有的\(|A_i|=\{0\}\),此时所有的\(A\)都有且仅有同一个元素\(0\),因此它们的并集也为\({0}\),因此上述所有集合的大小均为\(1\),与\(\varphi(1)=1\)一同代入上式可得:
\[1=1-\sum_{d|x}\varphi(d) \]\[\sum_{d|x}\varphi(d)=0 \ \ (x> 1) \]证毕.
另外,特殊的,我们发现\(\varphi(1)=1\),因此有性质:
\[\sum_{d|x}\mu(d) = 1 \]当且仅当\(x=1\)成立.
下面来看莫比乌斯反演如何证明.
莫比乌斯反演:若\(f(x)=\sum_{d|x}g(d)\),则有\(g(x)=\sum_{d|x}\varphi(\frac{x}{d})f(d)\).
我们尝试将条件式代入右式,发现有:
\[\sum_{d|x}\varphi(\frac{x}{d})f(d) =\sum_{d|x}\varphi(\frac{x}{d})\sum_{k|d}g(k) \]我们考虑每一个\(g(x)\)对总答案的贡献,发现每一个满足\(mk | x\)的二元组\((m,k)\)对答案都有\(g(k)\varphi(m)\)的贡献,更换求和顺序,有:
\[\sum_{d|x}\varphi(\frac{x}{d})f(d) =\sum_{k|x}g(k)\sum_{m|(x/k)}\varphi(m) \]由于上面我们证出的性质,\(\frac{x}{k}\neq1\)时,\(\sum_{m|(x/k)}\varphi(m)=0\),因此对所有\(k\neq x\),\(k\)对答案都没有贡献,只需令\(k=x\)即可.因此有:
\[ \sum_{d|x}\varphi(\frac{x}{d})f(d) =\sum_{k|x}g(k)\sum_{m|(x/k)}\varphi(m)=g(x) \]即证.
4.小结
容斥定理有化并为交的功能,在许多情况下,一些有性质的集合做交集仍有很好的性质,而作并集就会变得乱七八糟.举个例子,\(A=\{d|d=2k,k\in\mathbb{Z}\},B=\{d|d=3k,k\in\mathbb{Z}\}\),这时就有\(A\cap B=\{d|d=6k,k\in\mathbb{Z}\}\),这与\(A,B\)的形式是一致的.我们利用这样的性质,化并为交地求出了欧拉函数的定义式.另外的,我们发现莫比乌斯函数\(\varphi(x)\)与容斥原理有千丝万缕的联系,因此考虑其实际意义,找到这个函数的性质,进而证明了莫比乌斯反演.
标签：mu,frac,sum,容斥,varphi,初步,原理,质数 From： https://www.cnblogs.com/snowycat1234/p/18144339