10 欧拉函数 Φ(N)\VARPHI(N)Φ(N)
学习目标
学完这一节，你应该能够：
* 理解欧拉函数 φ(n)\varphi(n)φ(n) 的含义；
* 会求素数和质数幂的欧拉函数；
* 理解一般公式为什么只和不同的质因子有关；
* 一步一步理解一般公式的来源；
* 看懂求单个 φ(n)\varphi(n)φ(n) 的 C++ 代码。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 欧拉函数的定义
欧拉函数：
φ(n)\varphi(n) φ(n)
表示：
> 在 1,2,…,n1,2,\dots,n1,2,…,n 中，与 nnn 互质的正整数有多少个。
例如：
n=8n=8 n=8
从 1 到 8：
1,2,3,4,5,6,7,81,2,3,4,5,6,7,8 1,2,3,4,5,6,7,8
其中与 8 互质的有：
1,3,5,71,3,5,7 1,3,5,7
所以：
φ(8)=4\boxed{\varphi(8)=4} φ(8)=4
当 n>1n>1n>1 时，nnn 本身与 nnn 的最大公约数是 nnn，所以它不会被计入。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 素数的情况
如果 ppp 是素数，那么：
1,2,…,p−11,2,\dots,p-1 1,2,…,p−1
都与 ppp 互质。
一共有：
p−1p-1 p−1
个。
因此：
φ(p)=p−1\boxed{\varphi(p)=p-1} φ(p)=p−1
例如：
φ(7)=6\varphi(7)=6 φ(7)=6
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 质数幂的情况
现在考虑：
n=pkn=p^k n=pk
其中 ppp 是素数。
pkp^kpk 只有一个不同的质因子：
pp p
所以一个整数与 pkp^kpk 不互质，当且仅当它也是 ppp 的倍数。
从 1 到 pkp^kpk 中，ppp 的倍数是：
p,2p,3p,…,pk−1pp,2p,3p,\dots,p^{k-1}p p,2p,3p,…,pk−1p
一共有：
pk−1p^{k-1} pk−1
个。
所以：
φ(pk)=pk−pk−1\varphi(p^k)=p^k-p^{k-1} φ(pk)=pk−pk−1
也可以写成：
φ(pk)=pk(1−1p)\boxed{\varphi(p^k)=p^k\left(1-\frac1p\right)} φ(pk)=pk(1−p1 )
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 一般的 NNN 为什么只看不同的质因子
例如：
12=22×312=2^2\times3 12=22×3
一个整数 xxx 与 12 互质，当且仅当：
* xxx 不是 2 的倍数；
* xxx 不是 3 的倍数。
这里并不需要额外要求“不能被 222^222 整除”。
因为只要 xxx 能被 2 整除，它就已经和 12 拥有公共因子 2，不再互质。
因此判断是否互质时，真正重要的是：
2, 32,\ 3 2, 3
这两个不同的质因子。
一般地，如果：
n=p1a1p2a2⋯pkakn=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} n=p1a1 p2a2 ⋯pkak
那么一个整数与 nnn 互质，当且仅当它不被任何：
p1,p2,…,pkp_1,p_2,\dots,p_k p1 ,p2 ,…,pk
整除。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 先看只有两个不同质因子的情况
假设：
n=paqbn=p^aq^b n=paqb
其中 p,qp,qp,q 是不同的素数。
从 1 到 nnn 一共有：
nn n
个整数。
其中 ppp 的倍数有：
np\frac np pn
个。
qqq 的倍数有：
nq\frac nq qn
个。
如果直接计算：
n−np−nqn-\frac np-\frac nq n−pn −qn
会出现一个问题。
同时是 ppp 和 qqq 倍数的数，也就是 pqpqpq 的倍数，被减掉了两次。
而 pqpqpq 的倍数有：
npq\frac n{pq} pqn
个。
所以必须加回来一次：
φ(n)=n−np−nq+npq\varphi(n)=n-\frac np-\frac nq+\frac n{pq} φ(n)=n−pn −qn +pqn
把 nnn 提出来：
φ(n)=n(1−1p−1q+1pq)\varphi(n)=n\left(1-\frac1p-\frac1q+\frac1{pq}\right) φ(n)=n(1−p1 −q1 +pq1 )
括号可以分解：
1−1p−1q+1pq=(1−1p)(1−1q)1-\frac1p-\frac1q+\frac1{pq}=\left(1-\frac1p\right)\left(1-\frac1q\right) 1−p1 −q1 +pq1 =(1−p1 )(1−q1 )
因此：
φ(n)=n(1−1p)(1−1q)\boxed{\varphi(n)=n\left(1-\frac1p\right)\left(1-\frac1q\right)} φ(n)=n(1−p1 )(1−q1 )
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 三个不同质因子时怎样一步一步数
如果：
n=paqbrcn=p^aq^br^c n=paqbrc
其中 p,q,rp,q,rp,q,r 是三个不同的素数，那么一个数与 nnn 互质，就必须同时满足：
* 不是 ppp 的倍数；
* 不是 qqq 的倍数；
* 不是 rrr 的倍数。
从 nnn 个整数开始。
先减去 ppp 的倍数：
−np-\frac np −pn
再减去 qqq 的倍数：
−nq-\frac nq −qn
再减去 rrr 的倍数：
−nr-\frac nr −rn
但是这样会把同时含两个质因子的数重复减掉。
例如 pqpqpq 的倍数既被“去掉 ppp 的倍数”减过一次，又被“去掉 qqq 的倍数”减过一次，所以要加回来一次：
+npq+\frac n{pq} +pqn
同理还要加回来：
+npr+\frac n{pr} +prn
和：
+nqr+\frac n{qr} +qrn
现在再看同时是 p,q,rp,q,rp,q,r 倍数的数。
它们在前面的三个“减法”中一共被减了 3 次，又在三个“加法”中一共被加了 3 次。
这样等于一次都没有删掉。
但这些数显然不与 nnn 互质，所以还要再减掉一次：
−npqr-\frac n{pqr} −pqrn
因此：
φ(n)=n−np−nq−nr+npq+npr+nqr−npqr\varphi(n)=n-\frac np-\frac nq-\frac nr+\frac n{pq}+\frac n{pr}+\frac n{qr}-\frac n{pqr} φ(n)=n−pn −qn −rn +pqn +prn +qrn −pqrn
把 nnn 提出来：
φ(n)=n(1−1p−1q−1r+1pq+1pr+1qr−1pqr)\varphi(n)=n\left(1-\frac1p-\frac1q-\frac1r+\frac1{pq}+\frac1{pr}+\frac1{qr}-\frac1{pqr}\right) φ(n)=n(1−p1 −q1 −r1 +pq1 +pr1 +qr1 −pqr1 )
而：
(1−1p)(1−1q)(1−1r)=1−1p−1q−1r+1pq+1pr+1qr−1pqr\left(1-\frac1p\right)\left(1-\frac1q\right)\left(1-\frac1r\right)=1-\frac1p-\frac1q-\frac1r+\frac1{pq}+\frac1{pr}+\frac1{qr}-\frac1{pqr} (1−p1 )(1−q1 )(1−r1 )=1−p1 −q1 −r1 +pq1 +pr1 +qr1 −pqr1
所以：
φ(n)=n(1−1p)(1−1q)(1−1r)\boxed{\varphi(n)=n\left(1-\frac1p\right)\left(1-\frac1q\right)\left(1-\frac1r\right)} φ(n)=n(1−p1 )(1−q1 )(1−r1 )
这说明乘积公式中的每一项，都在处理“删除倍数时可能重复计算”的问题。
有更多不同质因子时，规律完全相同，只是需要继续处理更多种重复情况。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. 一般公式
如果：
n=p1a1p2a2⋯pkakn=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k} n=p1a1 p2a2 ⋯pkak
其中：
p1,p2,…,pkp_1,p_2,\dots,p_k p1 ,p2 ,…,pk
是 nnn 的所有不同质因子，那么：
φ(n)=n(1−1p1)(1−1p2)⋯(1−1pk)\boxed{\varphi(n)=n\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\cdots\left(1-\frac1{p_k}\right)} φ(n)=n(1−p1 1 )(1−p2 1 )⋯(1−pk 1 )
每一个不同质因子只出现一次。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8. 用 N=12N=12N=12 检查公式
因为：
12=22×312=2^2\times3 12=22×3
所以不同质因子是：
2, 32,\ 3 2, 3
公式：
φ(12)=12(1−12)(1−13)\varphi(12)=12\left(1-\frac12\right)\left(1-\frac13\right) φ(12)=12(1−21 )(1−31 )
计算：
φ(12)=12×12×23=4\varphi(12)=12\times\frac12\times\frac23=4 φ(12)=12×21 ×32 =4
实际与 12 互质的数是：
1,5,7,111,5,7,11 1,5,7,11
正好 4 个。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
9. 再看一个例子：Φ(18)\VARPHI(18)Φ(18)
因为：
18=2×3218=2\times3^2 18=2×32
不同质因子只有：
2, 32,\ 3 2, 3
所以：
φ(18)=18(1−12)(1−13)\varphi(18)=18\left(1-\frac12\right)\left(1-\frac13\right) φ(18)=18(1−21 )(1−31 )
得到：
φ(18)=18×12×23=6\varphi(18)=18\times\frac12\times\frac23=6 φ(18)=18×21 ×32 =6
因此：
φ(18)=6\boxed{\varphi(18)=6} φ(18)=6
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
10. C++ 求单个 Φ(N)\VARPHI(N)Φ(N)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
11. 为什么 ANS 一开始等于 NNN
公式是：
φ(n)=n(1−1p1)(1−1p2)⋯\varphi(n)=n\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\cdots φ(n)=n(1−p1 1 )(1−p2 1 )⋯
所以先令：
然后每发现一个新的不同质因子 ppp，就把：
1−1p1-\frac1p 1−p1
乘进去。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
12. 为什么写成 ANS / P * (P - 1)
因为：
1−1p=p−1p1-\frac1p=\frac{p-1}{p} 1−p1 =pp−1
所以：
ans(1−1p)=ans⋅p−1pans\left(1-\frac1p\right)=ans\cdot\frac{p-1}{p} ans(1−p1 )=ans⋅pp−1
代码写成：
这里在处理质因子 ppp 时，当前的 ans 能被 ppp 整除，因此先除再乘可以保持整数运算。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
13. 为什么要把同一个质因子全部除掉
发现：
p∣np\mid n p∣n
以后：
会把 ppp 的所有次数全部除掉。
例如：
72=23×3272=2^3\times3^2 72=23×32
发现质因子 2 后：
72→36→18→972\rightarrow36\rightarrow18\rightarrow9 72→36→18→9
这样 2 就不会被重复当成新的质因子处理。
因为欧拉函数公式中，每一个不同质因子只需要出现一次。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
14. 为什么只需要试到平方根附近
如果一个大于 1 的整数是合数，那么它至少有一个质因子不超过它的平方根。
否则如果所有非 1 因子都大于平方根，那么任意两个这样的因子相乘都会大于原数，不可能得到原数。
所以不断试除小质因子，就可以把可以分解的部分找出来。
需要注意：代码循环条件中的 n 会随着质因子被除掉而不断变小，因此这里判断的是“当前剩余的 nnn”。
代码写成：
而不是直接写：
是为了避免当整数很大时，p * p 自身先发生溢出。两种写法在不溢出的情况下表达的是同一个条件。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
15. 为什么最后还要判断 N > 1
循环结束以后，可能还剩下一个没有处理过的大质因子。
例如原来：
n=14n=14 n=14
先处理质因子 2：
14→714\rightarrow7 14→7
剩下的 7 本身是质数。
它还没有进入欧拉函数公式，所以最后要判断：
这里剩下的 n 如果大于 1，就一定是还未处理的一个质因子。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
16. 小练习
练习 1
求：
φ(9)\varphi(9) φ(9)
练习 2
求：
φ(10)\varphi(10) φ(10)
练习 3
为什么 n=pkn=p^kn=pk 时，与 nnn 不互质的数恰好是 ppp 的倍数？
练习 4
为什么欧拉函数的一般公式中，同一个质因子只出现一次？
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
17. 答案
练习 1
φ(9)=9−3=6\varphi(9)=9-3=6 φ(9)=9−3=6
练习 2
φ(10)=10(1−12)(1−15)=4\varphi(10)=10\left(1-\frac12\right)\left(1-\frac15\right)=4 φ(10)=10(1−21 )(1−51 )=4
练习 3
因为 pkp^kpk 唯一的质因子是 ppp。一个数与 pkp^kpk 有大于 1 的公共因子，当且仅当它也含有质因子 ppp。
练习 4
因为判断是否与 nnn 互质，只关心某个质因子是否出现，不关心这个质因子在 nnn 中出现多少次。
