欧拉函数#

欧拉函数 ，表示 内与 互质的数的个数。对于质数 显然有 。特殊地，。欧拉函数是一个积性函数，对任意互质的数 ，都有 。不互质时，如果 为奇数，那么有 。

如果 可以用算术基本定理分解成 的形式，那么 。注意，若 可以被同一个质数反复除尽，即存在一个 和 使得 ，计算时同样只对这个质数计算一次贡献。

证明：

正难则反，考虑用 内的所有数的个数减去不互质的数的个数。

因为每个大于 的自然数都可以分解为若干质数之积，因此我们只需要考虑小于等于 的所有质因子，这一步类似于埃氏筛的想法。那么能被 整除的数就有 个，进而，得到第一个式子：

但是有一个小问题——如果 或诸如此类的数，那么在计算贡献时会被 和 同时计入，显然结果小于正确答案。此时我们就需要引入“容斥原理”来帮我们解决这个问题了。来看一个例子（小学奥数题）：

假设被 整除的数分别构成三个集合 ，那么我们在用 计算结果时（ 记号表示集合元素个数），两个集合间的交集部分总共会被计入两次，最中间三个集合的交集总共会被计入三次，而我们希望的是每个部分只计一次。此时可以用上边算出的和减去两两集合之间的交集，那么最中间又会被减去三次，因而最终再加上一次中间部分，就得到了正确答案。也就是说本例的结果为：

特别的，形如上例问题的结果可以用以下公式算出：

因此我们在欧拉函数的计算中，也可以引入容斥原理。我们需要加上能被任意两个不同质数之积整除的数的个数，再减去能同时被三个不同质数之积整除的，以此类推。最终经过一些奇妙的化简（或者根本就是猜了一个结果然后拆括号检验的，正难则反懂不懂），得到如下计算公式：

代码实现时，通常把 等价变形为 ，然后先除后乘，以保证整除。

1
int eular(int x) {
2
    int res = x;
3
    for (int i = 2; i * i <= x; i++) {
4
        if (x % i == 0) {
5
            res = res / i * (i - 1);
6
            while (x % i == 0) x /= i;
7
        }
8
    }
9
    if (x > 1) res = res / x * (x - 1);
10
    return res;
11
}

欧拉函数的递推#

本质是在筛质数的过程中顺便维护一定区间内的数的欧拉函数值，这就需要用到欧拉函数作为积性函数的性质了。

线性筛/埃氏筛在筛质数的过程中，有一步是标记掉质数的所有倍数，根据算术基本定理，所有合数都可以被如此标记掉。假如当前在筛 ，大部分情况下 是可以保证的，此时 。在这两种质数筛中，有一个特殊情况是 ，此时 。总的时间复杂度是线性的。

1
int phi[N], primes[N];
2
bool st[N];
3
int idx = 0;
4

5
void sieve(int lim) {
6
    phi[1] = 1;
7
    for (int i = 2; i <= lim; i++) {
8
        if (!st[i]) {
9
            primes[++idx] = i;
10
            phi[i] = i - 1;
11
        }
12
        st[i] = true;
13
        for (int j = 1; i * primes[j] <= lim; j++) {
14
            phi[i * primes[j]] = phi[i] * (primes[j] - 1);
15
            st[i * primes[j]] = true;
16
            if (i % primes[j] == 0) {
17
                phi[i * primes[j]] = phi[i] * primes[j];
18
                break;
19
            }
20
        }
21
    }
22
}

欧拉函数的实例#

一个排列整齐的点阵，请问从某个角看去，视野内总共有多少个点？（不包括自己）

观察可得，图是有对称性的。那么沿对角线划分成上下两个对称的部分，对于两个点 和 ，显然当 互质且 互质时才能为答案贡献 。因此只需求互质对的数目即可，答案就是 。