E001. Euler function

Источник: e-maxx.ru/algo, страница PDF 8.

Định nghĩa

Euler function

(иногда обозначаемая

или

) — это количество чисел от

до

,

взаимно простых с

. Иными словами, это количество таких чисел в отрезке

, наибольший общий делитель

которых с

равен единице. Несколько первых значений этой функции (A000010 в энциклопедии OEIS):

Свойства

Три следующих простых свойства функции Эйлера — достаточны, чтобы научиться вычислять её для любых чисел:

● Если

— простое number, то

.

(Это очевидно, т.к. любое number, кроме самого

, взаимно просто с ним.)

● Если

— простое,

— натуральное number, то

.

(Поскольку с numberм

не взаимно просты только числа вида

, которых

штук.)

● Если

и

взаимно простые, то

("мультипликативность" функции Эйлера). (Этот факт следует из китайской теоремы об остатках. Рассмотрим произвольное number

. Обозначим через

и

остатки от деления

на

и

соответственно. Тогда

взаимно просто с

тогда и только тогда, когда

взаимно просто с

и с

по отдельности, или, что то же самое,

взаимно просто с

и

взаимно просто с

. Применяя китайскую теорему об остатках, получаем, что любой паре чисел

и

взаимно однозначно соответствует number

, что и завершает Chứng minh.)

Отсюда можно получить функцию Эйлера для любого

через его факторизацию (разложение

на

простые сомножители):

если

(где все

— простые), то

Cài đặt

Простейший код, вычисляющий функцию Эйлера, факторизуя number elementарным методом за :

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;

} Ключевое место для вычисление функции Эйлера — это нахождение факторизации числа

. Его

можно осуществить за время, значительно меньшее

: см. Эффективные Thuật toánы факторизации.

Приложения функции Эйлера

Самое известное и важное свойство функции Эйлера выражается в теореме Эйлера:

где

и

взаимно просты.

В частном случае, когда

простое, теорема Эйлера превращается в так называемую малую теорему Ферма: Теорема Эйлера достаточно часто встречается в практических приложениях, наVí dụ, см. Modular inverse в поле по модулю.

Задачи в online judges

Список задач, в которых it is required посчитать функцию Эйлера,либо воспользоваться теоремой Эйлера, либо по значению функции Эйлера восстанавливать исходное number:

● UVA #10179 "Irreducible Basic Fractions" [Complexity: низкая]

● UVA #10299 "Relatives" [Complexity: низкая]

● UVA #11327 "Enumerating Rational Numbers" [Complexity: средняя]

● TIMUS #1673 "Допуск к экзамену" [Complexity: высокая]