P209: Calculate Euler's totient function phi(m)

计算欧拉函数。

在数论中，对正整数n，欧拉函数 ${\displaystyle \varphi (n)}$是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。

例如 ${\displaystyle \varphi (8)=4}$，因为1,3,5,7均和8互质。

欧拉函数实际上是模n的同余类所构成的乘法群（即环 ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$的所有单位元组成的乘法群）的阶。这个性质与拉格朗日定理一起构成了欧拉定理的证明。^wiki-euler

照例先写测试用例：

欧拉函数的值

$\varphi (1)=1$（小于等于1的正整数中唯一和1互质的数就是1本身）。

若n是质数p的k次幂， ${\displaystyle \varphi (n)=\varphi (p^{k})=p^{k}-p^{k-1}=(p-1)p^{k-1}}$，因为除了p的倍数外，其他数都跟n互质。

欧拉函数是积性函数，即是说若m,n互质， ${\displaystyle \varphi (mn)=\varphi (m)\varphi (n)}$。证明：设A, B, C是跟m, n, mn互质的数的集，据中国剩余定理，${\displaystyle A\times B}$和${\displaystyle C}$可建立双射(一一对应)的关系。（或者也可以从初等代数角度给出欧拉函数积性的简单证明） 因此 ${\displaystyle \varphi (n)}$的值使用算术基本定理便知，

若 ${\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}}$

则 ${\displaystyle \varphi (n)=\prod _{i=1}^{r}p_{i}^{k_{i}-1}(p_{i}-1)=\prod _{p\mid n}p^{\alpha _{p}-1}(p-1)=n\prod _{p|n}\left(1-{\frac {1}{p}}\right)}$。

其中 ${\displaystyle \alpha _{p}}$是使得 ${\displaystyle p^{\alpha }}$整除 ${\displaystyle n}$的最大整数 ${\displaystyle \alpha }$（这里 ${\displaystyle \alpha _{p_{i}}=k_{i}}$。

例如 ${\displaystyle \varphi (72)=\varphi (2^{3}\times 3^{2})=2^{3-1}(2-1)\times 3^{2-1}(3-1)=2^{2}\times 1\times 3\times 2=24}$ ^wiki-euler

由欧拉函数的性质可知，先求出其所有质因数，再求出每一个质因数的$(p-1)p^{k-1}$（p为质因数，k为p在所有质因数中重复的之数），最后把结果累乘起来即为函数的值。

完整的代码实现：

在P203中已经实现了分解质因数，这里可以直接重用。prime_factors_mult返回的是列表，其中每一个元素都二元组，二元组中第一个元素为质因数，第二个元素为质因数的幂。按公式$(p-1)p^{k-1}$计算每一个二元组。最后把结果用functools.reduce累乘起来，就是欧拉函数的值。

参考文献

^wiki-euler. https://zh.wikipedia.org/wiki/欧拉函数 ↩