欧拉函数
思想
\(\varphi(n)\) 表示的是 \(1\sim n\) 中与 \(n\) 互质的个数。
怎么求 \(\varphi(n)\) 呢？
先将 \(n\) 质因数分解：\(n = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\)，那么 \(\varphi(n) = n\left(1 - \dfrac{1}{p_1}\right)\left(1 - \dfrac{1}{p_2}\right)\cdots \left(1 - \dfrac{1}{p_k}\right)\)。
证明：
要保留所有 \(1\sim n\) 中与 \(n\) 互质的数字，需要用到容斥原理，如下：
- 删除 \(1\sim n\) 中所有 \(p_1, p_2, \cdots p_k\) 的倍数；
- 加上所有 \(p_ip_j\) 的倍数（\(i, j\) 互不相同）；
- 减去左右 \(p_ip_jp_k\) 的倍数（\(i, j, k\) 互不相同）；
- 加上所有 \(p_ip_jp_kp_l\) 的倍数 （\(i, j, k, l\) 互不相同）。
然后是减去 5 个质因数相乘，加上 6 个质因数相乘，以此类推。
展开 \(\varphi(n) = n\left(1 - \dfrac{1}{p_1}\right)\left(1 - \dfrac{1}{p_2}\right)\cdots \left(1 - \dfrac{1}{p_k}\right)\)，然后发现就是上面那些操作。
也可以写成：\(\varphi(n) = n\cdot \dfrac{p_1 - 1}{p_1}\cdot \dfrac{p_2 - 1}{p_2}\cdots \dfrac{p_n - 1}{p_n}\)（感谢 @沃若 的建议）。
代码
void solve() {
int x, ans;
cin >> x;
ans = x;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) {
(ans /= i) *= (i - 1);
while (x % i == 0) x /= i;
}
}
if (x > 1) (ans /= x) *= (x - 1);
cout << ans << '\n';
}
\(O(n)\) 求欧拉函数
思想
即在线性筛的过程中求出所有数字的 \(\varphi\)。
首先，如果 \(x\) 是个质数，\(\varphi(x) = x - 1\)，因为在 \(1\sim x\) 中除了 \(x\) 都与 \(x\) 互质。
然后，想一想怎么求 \(phi(i \cdot j)\)，其中 \(i\) 是一个正数，\(j\) 是一个质数且是 \(i\cdot j\) 的最小质因数。
首先，如果 \(i\bmod j \ne 0\)，那么证明 \(i\) 中也没有 \(j\)，那么根据上面的公式：
\[\varphi(n) = n\left(1 - \dfrac{1}{p_1}\right)\left(1 - \dfrac{1}{p_2}\right)\cdots \left(1 - \dfrac{1}{p_k}\right) \]我们发现 \(j\) 是第一次出现，所以要在 \(\varphi(i)\) 乘上 \(j \cdot \left(1 - \dfrac{1}{j}\right)\)，根据乘法分配率，就是乘上 \(j - 1\)。
然后，根据上面的公式，假设 \(i \bmod j = 0\)，那么证明 \(i\) 中已经有 \(j\) 了，已经出现过 \(\left(1 - \dfrac{1}{j}\right)\)，所以不需要再乘了，我们只要乘上 \(j\) 就可以了。
特殊的，\(\varphi(1) = 1\)。
代码
const int N = 1000010;
bool inp[N];
int prime[N], cnt;
int phi[N];
void getprime(int n) {
inp[0] = inp[1] = true;
phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!inp[i]) {
prime[++cnt] = i;
phi[i] = i - 1;
}
for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
inp[i * prime[j]] = true;
if (i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
}