E001. Функция Эйлера
Источник: e-maxx.ru/algo, страница PDF 8.
Определение
Функция Эйлера
(иногда обозначаемая
или
) — это количество чисел от
до
,
взаимно простых с
. Иными словами, это количество таких чисел в отрезке
, наибольший общий делитель
которых с
равен единице. Несколько первых значений этой функции (A000010 в энциклопедии OEIS):
Свойства
Три следующих простых свойства функции Эйлера — достаточны, чтобы научиться вычислять её для любых чисел:
● Если
— простое число, то
.
(Это очевидно, т.к. любое число, кроме самого
, взаимно просто с ним.)
● Если
— простое,
— натуральное число, то
.
(Поскольку с числом
не взаимно просты только числа вида
, которых
штук.)
● Если
и
взаимно простые, то
("мультипликативность" функции Эйлера). (Этот факт следует из китайской теоремы об остатках. Рассмотрим произвольное число
. Обозначим через
и
остатки от деления
на
и
соответственно. Тогда
взаимно просто с
тогда и только тогда, когда
взаимно просто с
и с
по отдельности, или, что то же самое,
взаимно просто с
и
взаимно просто с
. Применяя китайскую теорему об остатках, получаем, что любой паре чисел
и
взаимно однозначно соответствует число
, что и завершает доказательство.)
Отсюда можно получить функцию Эйлера для любого
через его факторизацию (разложение
на
простые сомножители):
если
(где все
— простые), то
Реализация
Простейший код, вычисляющий функцию Эйлера, факторизуя число элементарным методом за :
int phi (int n) {int result = n;for (int i=2; i*i<=n; ++i)if (n % i == 0) {while (n % i == 0)n /= i;
result -= result / i;
}
if (n > 1)result -= result / n;
return result;} Ключевое место для вычисление функции Эйлера — это нахождение факторизации числа
. Его
можно осуществить за время, значительно меньшее
: см. Эффективные алгоритмы факторизации.
Приложения функции Эйлера
Самое известное и важное свойство функции Эйлера выражается в теореме Эйлера:
где
и
взаимно просты.
В частном случае, когда
простое, теорема Эйлера превращается в так называемую малую теорему Ферма: Теорема Эйлера достаточно часто встречается в практических приложениях, например, см. Обратный элемент в поле по модулю.
Задачи в online judges
Список задач, в которых требуется посчитать функцию Эйлера,либо воспользоваться теоремой Эйлера, либо по значению функции Эйлера восстанавливать исходное число:
● UVA #10179 "Irreducible Basic Fractions" [сложность: низкая]
● UVA #10299 "Relatives" [сложность: низкая]
● UVA #11327 "Enumerating Rational Numbers" [сложность: средняя]
● TIMUS #1673 "Допуск к экзамену" [сложность: высокая]
C# решение
auto-draft, проверить перед отправкойusing System;
using System.Collections.Generic;
using System.Linq;
public static class AlgorithmDraft
{
// Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
int phi (int n) {
int result = n;
for (int i=2; i*i<=n; ++i)
if (n % i == 0) {
while (n % i == 0)
n /= i;
result -= result / i;
}
if (n > 1)
result -= result / n;
return result;
}
}C++ решение
сопоставлено/оригиналint phi (int n) {
int result = n;
for (int i=2; i*i<=n; ++i)
if (n % i == 0) {
while (n % i == 0)
n /= i;
result -= result / i;
}
if (n > 1)
result -= result / n;
return result;
}Java решение
auto-draft, проверить перед отправкойimport java.util.*;
import java.math.*;
public class AlgorithmDraft {
// Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
int phi (int n) {
int result = n;
for (int i=2; i*i<=n; ++i)
if (n % i == 0) {
while (n % i == 0)
n /= i;
result -= result / i;
}
if (n > 1)
result -= result / n;
return result;
}
}Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.