E001. Euler function
Источник: e-maxx.ru/algo, страница PDF 8.
정의
Euler function
(иногда обозначаемая
или
) — это количество чисел от
до
,
взаимно простых с
. Иными словами, это количество таких чисел в отрезке
, наибольший общий делитель
которых с
равен единице. Несколько первых значений этой функции (A000010 в энциклопедии OEIS):
Свойства
Три следующих простых свойства функции Эйлера — достаточны, чтобы научиться вычислять её для любых чисел:
● Если
— простое number, то
.
(Это очевидно, т.к. любое number, кроме самого
, взаимно просто с ним.)
● Если
— простое,
— натуральное number, то
.
(Поскольку с numberм
не взаимно просты только числа вида
, которых
штук.)
● Если
и
взаимно простые, то
("мультипликативность" функции Эйлера). (Этот факт следует из китайской теоремы об остатках. Рассмотрим произвольное number
. Обозначим через
и
остатки от деления
на
и
соответственно. Тогда
взаимно просто с
тогда и только тогда, когда
взаимно просто с
и с
по отдельности, или, что то же самое,
взаимно просто с
и
взаимно просто с
. Применяя китайскую теорему об остатках, получаем, что любой паре чисел
и
взаимно однозначно соответствует number
, что и завершает 증명.)
Отсюда можно получить функцию Эйлера для любого
через его факторизацию (разложение
на
простые сомножители):
если
(где все
— простые), то
구현
Простейший код, вычисляющий функцию Эйлера, факторизуя 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;} Ключевое место для вычисление функции Эйлера — это нахождение факторизации числа
. Его
можно осуществить за время, значительно меньшее
: см. Эффективные 알고리즘ы факторизации.
Приложения функции Эйлера
Самое известное и важное свойство функции Эйлера выражается в теореме Эйлера:
где
и
взаимно просты.
В частном случае, когда
простое, теорема Эйлера превращается в так называемую малую теорему Ферма: Теорема Эйлера достаточно часто встречается в практических приложениях, на예제, см. 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# 해법
자동 초안, 제출 전 검토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 해법
자동 초안, 제출 전 검토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;
}
}Материал разбит как 알고리즘ическая 문제: изучить постановку, понять асимптотику и реализовать 알고리즘 на выбранном языке.
Vacancies for this task
활성 채용 with overlapping task tags are 표시됨.