Функция Эйлера φ(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
Примеры
Ввод:
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.
Ввод:
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. Следуйте условию и ограничениям выше.