欧拉函数#

欧拉函数 $\varphi(x)$，表示 $[1,x]$ 内与 $x$ 互质的数的个数。对于质数 $p$ 显然有 $\varphi(p)=p-1$。特殊地，$\varphi(1)=1$。欧拉函数是一个积性函数，对任意互质的数 $a,b$，都有 $\varphi(ab)=\varphi(a)\cdot\varphi(b)$。不互质时，如果 $x$ 为奇数，那么有 $\varphi(2n)=\varphi(n)$。

如果 $x$ 可以用算术基本定理分解成 $\prod\limits_{i=1}^{k}p_i^{c_i}$ 的形式，那么 $\varphi(x)=x(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots(1-\frac{1}{p_k})=x\prod\limits_{i=1}^{k}(1-\frac{1}{p_k})$。注意，若 $x$ 可以被同一个质数反复除尽，即存在一个 $p_i$ 和 $t>1$ 使得 $p_i^t\mid x$，计算时同样只对这个质数计算一次贡献。

证明：

正难则反，考虑用 $[1,n]$ 内的所有数的个数减去不互质的数的个数。

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

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

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

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

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

代码实现时，通常把 ${1-\frac{1}{p}}$ 等价变形为 $\frac{p-1}{p}$，然后先除后乘，以保证整除。

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
}

欧拉函数的递推#

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

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

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
}

欧拉函数的实例#

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

观察可得，图是有对称性的。那么沿对角线划分成上下两个对称的部分，对于两个点 $(a,b)$ 和 $(m,n)$，显然当 $a,b$ 互质且 $m,n$ 互质时才能为答案贡献 ${2}$。因此只需求互质对的数目即可，答案就是 ${2}\sum\limits_{i=1}^{n-1}\varphi(i)+1$。