数论补完计划 Part3 欧拉函数

欧拉函数

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

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

证明：

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

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

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

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

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

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

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

int eular(int x) {
    int res = x;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) res = res / x * (x - 1);
    return res;
}

欧拉函数的递推

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

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

int phi[N], primes[N];
bool st[N];
int idx = 0;

void sieve(int lim) {
    phi[1] = 1;
    for (int i = 2; i <= lim; i++) {
        if (!st[i]) {
            primes[++idx] = i;
            phi[i] = i - 1;
        }
        st[i] = true;
        for (int j = 1; i * primes[j] <= lim; j++) {
            phi[i * primes[j]] = phi[i] * (primes[j] - 1);
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) {
                phi[i * primes[j]] = phi[i] * primes[j];
                break;
            }
        }
    }
}