Функция Эйлера φ(n): как посчитать через факторизацию и для всех чисел решетом?
Встретил функцию Эйлера φ(n) — количество чисел от 1 до n, взаимно простых с n. Нужна для теоремы Эйлера и сокращения дробей. Как её быстро посчитать для одного числа и как — сразу для всех чисел до N?
2 ответа
Формула Эйлера через простые делители: если n = p1^a1 · ... · pk^ak, то
φ(n) = n · ∏ (1 − 1/p_i)
перемножая по всем различным простым делителям p_i. Вывод — из мультипликативности и того, что φ(p^a) = p^a − p^{a-1}.
Для одного числа за O(sqrt n):
long long phi(long long n) {
long long result = n;
for (long long p = 2; p * p <= n; p++)
if (n % p == 0) {
while (n % p == 0) n /= p;
result -= result / p; // умножение на (1 - 1/p)
}
if (n > 1) result -= result / n; // оставшийся простой
return result;
}
Обрати внимание: result -= result / p — это и есть result · (1 - 1/p), записанное без дробей, чтобы не терять точность. Сложность O(sqrt n).
Для всех i = 1..N за O(N log log N) — решетом, инициализируем phi[i] = i и для каждого простого p проходим по кратным:
vector<int> phi(N+1);
for (int i = 0; i <= N; i++) phi[i] = i;
for (int p = 2; p <= N; p++)
if (phi[p] == p) // p простое
for (int j = p; j <= N; j += p)
phi[j] -= phi[j] / p;
Дополню про теорему Эйлера: если gcd(a, m) = 1, то a^{φ(m)} ≡ 1 (mod m). Это обобщение малой теоремы Ферма (для простого m, φ(m) = m-1). Практическое применение — обратный элемент по составному модулю: a^{-1} ≡ a^{φ(m)-1} (mod m). И ещё приведение огромных показателей: a^b ≡ a^{b mod φ(m)} (mod m) при gcd(a,m)=1 — спасает, когда b само задано как башня степеней.