E001. Euler function
Источник: e-maxx.ru/algo, страница PDF 8.
Definition
Euler function
(иногда обозначаемая
или
) — это количество чисел от
до
,
взаимно простых с
. Иными словами, это количество таких чисел в отрезке
, наибольший общий делитель
которых с
равен единице. Несколько первых значений этой функции (A000010 в энциклопедии OEIS):
Свойства
Три следующих простых свойства функции Эйлера — достаточны, чтобы научиться вычислять её для любых чисел:
● Если
— простое number, то
.
(Это очевидно, т.к. любое number, кроме самого
, взаимно просто с ним.)
● Если
— простое,
— натуральное number, то
.
(Поскольку с numberм
не взаимно просты только числа вида
, которых
штук.)
● Если
и
взаимно простые, то
("мультипликативность" функции Эйлера). (Этот факт следует из китайской теоремы об остатках. Рассмотрим произвольное number
. Обозначим через
и
остатки от деления
на
и
соответственно. Тогда
взаимно просто с
тогда и только тогда, когда
взаимно просто с
и с
по отдельности, или, что то же самое,
взаимно просто с
и
взаимно просто с
. Применяя китайскую теорему об остатках, получаем, что любой паре чисел
и
взаимно однозначно соответствует number
, что и завершает Proof.)
Отсюда можно получить функцию Эйлера для любого
через его факторизацию (разложение
на
простые сомножители):
если
(где все
— простые), то
Implementation
Простейший код, вычисляющий функцию Эйлера, факторизуя 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;} Ключевое место для вычисление функции Эйлера — это нахождение факторизации числа
. Его
можно осуществить за время, значительно меньшее
: см. Эффективные Algorithmы факторизации.
Приложения функции Эйлера
Самое известное и важное свойство функции Эйлера выражается в теореме Эйлера:
где
и
взаимно просты.
В частном случае, когда
простое, теорема Эйлера превращается в так называемую малую теорему Ферма: Теорема Эйлера достаточно часто встречается в практических приложениях, наExample, см. 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: высокая]
C# solution
auto-draft, review before submitusing 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++ solution
matched/originalint 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 solution
auto-draft, review before submitimport 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;
}
}Материал разбит как Algorithmическая Task: изучить постановку, понять асимптотику и реализовать Algorithm на выбранном языке.
Vacancies for this task
Active vacancies with overlapping task tags are shown.