欧拉函数

在数论领域中，欧拉函数是一种重要的概念，它在解决许多数学问题和密码学中起着关键的作用。本文将介绍欧拉函数的定义、性质、求法 以及一些常见的应用，帮助读者更好地理解和应用欧拉函数。

欧拉函数的定义

欧拉函数，也称为欧拉降幂函数，是指小于或等于正整数 $n$ 的数中与 $n$ 互质 的数的个数。 欧拉函数通常用符号 $\phi(n)$ 表示。

欧拉函数的性质

• 若 $n$ 为质数，则 $\phi(n) = n - 1$，因为质数与小于它的所有数都互质。
• 若 $m$ 和 $n$ 互质，则 $\phi(mn) = \phi(m) * \phi(n)$，这是欧拉函数的积性性质。
• 对于任意正整数n，有 $\sum_{d \mid n} \phi(d) = n$，其中 $d$ 是 $n$ 的正因子。

欧拉函数的计算方法

对于给定的正整数 $n$，可以通过分解质因数的方法来计算 $\phi(n)$。假设 $n$ 的质因数分解为 ${p_1}^{a_1} \times {p_2}^{a_2} \times … \times {p_k}^{a_k}$，则有 \(\phi(n) = n \times \prod (1 - \dfrac{1}{p_i})\)

借助欧拉筛求一段数的欧拉函数。

#include <bits/stdc++.h>
using namespace std;
const int M = 2e5 + 5;
int minp[M], phi[M];
vector<int> primes;
int main() {
    for (int i = 2; i <= 2e5; i++) {
        if (!minp[i]) {
            minp[i] = i;
            phi[i] = i - 1;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (1ll * p * i > 2e5) {
                break;
            }
            minp[p * i] = p;
            phi[p * i] = i % p == 0 ? phi[i] * p : phi[i] * (p - 1);
            if (minp[i] == p) {
                break;
            }
        }
    }
    return 0;
}

求一个数的欧拉函数。

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

应用

P3601

一个比较板的欧拉函数题，不难发现其实只需要求一段数的欧拉函数就可以得到答案。那么只需要求出这些数的所有质因数。由于这些数可能很大，对于每个数用根号复杂度分解质因数是行不通的，考虑到这一段数的长度不超过 $10^6$，可以使用类似埃式筛的方法，对于所有不超过 $10^6$ 的质数（因为待求解的数不超过 $10^{12}$），考虑它们是否是这段数的质因数，向数段遍历一遍即可。最后如果这段数中的数没有变成 $1$，说明它们有一个大于 $10^6$ 的质因数，也就是它们现在的状态。

#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e6 + 5, mod = 666623333;
long long l, r, phi[maxN], num[maxN];
int minp[maxN];
vector<int> primes;
void init() {
    for (int i = 2; i <= 1e6; i++) {
        if (!minp[i]) {
            minp[i] = i;
            primes.push_back(i);
        }
        for (auto p : primes) {
            if (1ll * p * i > 1e6) {
                break;
            }
            minp[p * i] = p;
            if (minp[i] == p) {
                break;
            }
        }
    }
    for (int i = 0; i <= 1e6; i++) {
        phi[i] = 1;
    }
}
long long ceil(long long x, long long y) {
    return x % y == 0 ? x / y : x / y + 1;
}
int main() {
    init();
    cin >> l >> r;
    for (int i = 0; i <= r - l; i++) {
        num[i] = l + i;
    }
    for (auto p : primes) {
        for (int i = ceil(l, p), idx; i <= r / p; i++) {
            idx = 1ll * i * p - l;
            long long tmp = 1;
            num[idx] /= p;
            while (num[idx] % p == 0) {
                num[idx] /= p;
                tmp = tmp * p % mod;
            }
            phi[idx] = phi[idx] * tmp % mod * (p - 1) % mod;
        }
    }
    for (int i = 0; i <= r - l; i++) {
        if (num[i] != 1) {
            phi[i] = phi[i] * (num[i] - 1) % mod;
        }
    }
    long long res = 0;
    for (int i = 0; i <= r - l; i++) {
        res = (res + i + l - phi[i]) % mod;
    }
    cout << res;
    return 0;
}

CF776E

推导发现，答案实际上是对 $n$ 求 $\dfrac{k+1}{2}$ 次欧拉函数，n 为 $1$ 时欧拉函数恒为 $1$，不需要继续求下去了。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxN = 2e5 + 5, M = 1e6 + 5;
const int mod = 1000000007;
int minp[M];
vector<int> primes;
void init() {
    for (int i = 2; i <= 1e6; i++) {
        if (!minp[i]) {
            minp[i] = i;
            primes.push_back(i);
        }
        for (auto p : primes) {
            if (1ll * p * i > 1e6) {
                break;
            }
            minp[p * i] = p;
            if (minp[i] == p) {
                break;
            }
        }
    }
}
ll phi(ll x) {
    ll res = x;
    for (auto p : primes) {
        if (1ll * p * p > x) {
            break;
        }
        if (x % p == 0) {
            res = res / p * (p - 1);
        }
        while (x % p == 0) {
            x /= p;
        }
    }
    if (x > 1) {
        res = res / x * (x - 1);
    }
    return res;
}
int main() {
    init();
    ll n, k;
    cin >> n >> k;
    k = (k + 1) >> 1;
    for (ll i = 0; i < k && n > 1; i++) {
        n = phi(n);
    }
    cout << n % mod;
    return 0;
}