欧拉函数

一句话理解

欧拉函数 φ(n) 是 1..n-1 中与 n 互质的个数。

为什么要学

φ(p)=p-1，p 质数。

讲解

积性，可用线性筛。

例子

φ(10)=4：1,3,7,9。

常见错误

• φ(1)=1 易忘。
• 公式漏乘 (1-1/p)。