Все задачи
Средне Решено: 0 Процент решений: 0%

Функция Эйлера

Посчитайте, сколько целых чисел от 1 до n взаимно просты с n.

Чему вы научитесь

  • Находить различные простые делители n
  • Применять φ(n) = n × Π(1 − 1/p) только в целых числах
  • Обрабатывать n = 1 и простые n

Условие

Функция Эйлера φ(n) равна количеству целых k, для которых 1 ≤ k ≤ n и НОД(k, n) = 1. Например, φ(9) = 6, потому что числа 1, 2, 4, 5, 7 и 8 взаимно просты с 9.

Реализуйте eulers_totient(n).

Перебирать k по одному при n до 10^12 слишком долго. Воспользуйтесь формулой произведения: φ(n) = n × (1 − 1/p) по всем различным простым p, делящим n. Если считать в целых числах как n / p × (p − 1), дроби не понадобятся.

Входные данные

n: натуральное число.

Выходные данные

Верните φ(n). По определению φ(1) = 1.

Ограничения

1 ≤ n ≤ 10^12

Примеры

Пример 1
Ввод:
n = 36

Ожидаемый вывод:
expected = 12
Ввод:
long long n = 36;

Ожидаемый вывод:
long long expected = 12;
Ввод:
long n = 36;

Ожидаемый вывод:
long expected = 12;

Пояснение

36 = 2² × 3², поэтому φ(36) = 36 × (1 − 1/2) × (1 − 1/3) = 36 × 1/2 × 2/3 = 12.

Пример 2
Ввод:
n = 13

Ожидаемый вывод:
expected = 12
Ввод:
long long n = 13;

Ожидаемый вывод:
long long expected = 12;
Ввод:
long n = 13;

Ожидаемый вывод:
long expected = 12;

Пояснение

13 простое, поэтому все k от 1 до 12 взаимно просты с ним и φ(13) = 12.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Разложите n на множители пробным делением до √n.

Подсказка 2

Для каждого различного простого p замените результат на result / p × (p − 1); сначала делите, чтобы значение оставалось небольшим.

Подсказка 3

Множитель больше 1, оставшийся после цикла, тоже простой.

Ожидаемая сложность

время O(√n), доп. память O(1)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.