给定一个整数 INLINECODE025b72a8，我们需要找到 欧拉 Totient 函数 的值，记作 Φ(n)。该函数 Φ(n) 表示小于或等于 INLINECODE4b33b665 且与 n 互质 的正整数的个数。
> 对于输入 n，欧拉 Totient 函数 Φ(n) 是集合 {1, 2, 3, …, n-1} 中与 n 互质的数的计数，即这些数与 n 的 GCD (最大公约数) 为 1。
>
> 如果 n 是一个正整数，且其质因数分解为：n = p1^{e1} \cdot p2^{e2} \cdot \ldots \cdot pk^{ek}
> 其中 p1, p2, \ldots, p_k 是 n 的不同质因数，那么：
> \phi(n) = n \cdot \left(1 – \frac{1}{p1}\right) \cdot \left(1 – \frac{1}{p2}\right) \cdot \ldots \cdot \left(1 – \frac{1}{p_k}\right).
> 输入： n = 11
> 输出： 10
> 解释： 从 1 到 11，1,2,3,4,5,6,7,8,9,10 都与 11 互质。
>
> 输入： n = 16
> 输出： 8
> 解释： 从 1 到 16，1,3,5,7,9,11,13,15 都与 16 互质。
目录
- [朴素方法] 迭代 GCD 法
- [期望方法] 欧拉乘积公式
- 欧拉 Totient 函数的一些有趣性质
[朴素方法] 迭代 GCD 法
> 一个简单的解决方案是遍历从 1 到 n-1 的所有数字，并计算与 n 的最大公约数为 1 的数字个数。下面是用于计算输入整数 n 的欧拉 Totient 函数的简单方法的实现。
C++
CODEBLOCK_4c1b37f1
Java
CODEBLOCK_522fbcc6
Python
CODEBLOCK_a9b275c0
C#
CODEBLOCK_e8d6bebb
JavaScript
CODEBLOCK_989db18c
输出
10
时间复杂度： O(n log n)
辅助空间： O(log min(a,b))，其中 a,b 是 gcd 函数的参数。
[期望方法] 欧拉乘积公式
这个想法基于欧拉乘积公式，该公式指出 totient 函数的值等于 n 的所有质因数 p 的乘积。
> 1) 将 result 初始化为 n
> 2) 考虑每一个数字 ‘p‘（其中 ‘p‘ 从 2 变化到 Φ(n)）。
> 如果 p 能整除 n，则执行以下操作
> a) 从 1 到 n 减去 p 的所有倍数 [p 的所有倍数
> 与 n 的 gcd 将大于 1（至少为 p）]
> b) 通过重复将 n 除以 p 来更新 n。
> 3) 如果约简后的 n 大于 1，则移除所有倍数
>