欧拉函数

定义

1~N中与N互质的数的个数称为欧拉函数，记为ϕ(N)。

若在算数基本定理中，N = p1^a1 * p2^a2 * ….. * pm^am。

ϕ(N) = N * (p1 - 1) / p1 * (p2 - 1) / p2 * …. * (pm - 1) / pm。

证明

欧拉函数的证明基于容质原理。

设N = p1^a1 * p2^a2 * p3^a3 * … *pk ^ak。

我们要找到1N中与N互质的数，就要去掉1N中所有N的因数及其倍数。例如在1~N中所有p1的倍数的个数就有 N / p1个，以此类推….

但倍数之间可能存在重复，若p1和p2的倍数之间存在重复，我们就需要减去他们的公倍数，即N / (p1 * p2)，以此类推…

最终形式：N - N / p1 - N / p2 - …. - N / pk + N / p1p2 + N / p1p3 + … - N / p1p2p3 - N / p1p2p4 - …. + N / p1p2p3….pk。

代码

复杂度 O(nlogn)

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int tt;
    cin >> tt;
    while (tt -- ){
        int x;
        cin >> x;

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

        cout << res << endl;
    }

    return 0;
}

筛法求欧拉函数

筛法求欧拉函数其实就是在线性筛的过程中顺便求出每个数的欧拉函数。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1123456;
typedef long long ll;

bool st[maxn];
int phi[maxn], primes[maxn]; // phi[i]表示i的欧拉函数
int cnt;

void get_euler(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i ++ ){
        if (!st[i]){
            phi[i] = i - 1;
            primes[cnt ++ ] = i;
        }
        for (int j = 0; primes[j] <= n / i; j ++ ){
            st[primes[j] * i] = 1;
            if (i % primes[j] == 0){
                phi[primes[j] * i] = phi[i] * primes[j];
                break;
            }
            else{
                phi[primes[j] * i] = phi[i] * (primes[j] - 1);
            }
        }
    }
}

int main()
{
    int n;
    cin >> n;
    
    get_euler(n);
    
    ll res = 0;
    for (int i = 1; i <= n; i ++ ){
        res += phi[i];
    }
    
    cout << res << endl;
    
    return 0;
}

这里解释一下phi[i]如何得到。

如果i是质数：显然，一个质数k的欧拉函数就是1~k-1。

如果i不是质数：如果i % primes[j] = 0，那么primes[j] * i这个数的欧拉函数其实可以由phi[i]得到。显然primes[j]是primes[j] * i的一个质因子，且primes[j]也是i的一个质因子，那么phi[i] = i * (1 - 1 / p1) * … * (1 - 1/ primes[j]) * …，(1 - 1/ primes[j])这一项必定已经包含，而欧拉函数i乘的项数与指数大小无关，只与质因子数量有关。例如phi[6] = 6 * (1 - 1 / 2) * (1 - 1 / 3)，phi[6 ^ 100] = 6 ^ 100 * (1 - 1 / 2) * (1 - 1 / 3)。因此:

phi[i] = i * (1 - 1 / p1) * ... * (1 - 1 / pk);
phi[primes[j] * i] = primes[j] * i * (1 - 1 / p1) * ... * (1 - 1 / pk);
phi[primes[j] * i] = primes[j] * phi[i]; // 化简

如果i % primes[j] != 0，那么

phi[i] = i * (1 - 1 / p1) * ... * (1 - 1 / pk);
phi[primes[j] * i] = primes[j] * i * (1 - 1 / p1) * ... * (1 - 1 / pk) * (1 - 1 / primes[j]);
phi[primes[j] * i] = phi[i] * (primes[j] - 1); // 化简