Task 74. Несократимая дробь
UniLecsЗадача: дробь x/n - называется правильной несократимой, если выполнены условия:
1. 0 < X < N
2. НОД(X, N) = 1
Входные данные: N - натуральное число, где N < 10^6.
Вывод: вывести кол-во правильных несократимых дробей со знаменателем N.
Пример:
1. N = 11, Result = 10
2. N = 12, Result = 4
3. N = 17, Result = 16
Идея: воспользуемся функцией Эйлера и ее свойствами:
Функция Эйлера f(n) - равна количеству натуральных чисел, меньших n и взаимно простых с ним.
Т.е. значение функции Эйлера f(N) и будет кол-вом правильных несократимых дробей.
Давайте рассмотрим пример для значения N = 12.
Для числа 12 существует 4 меньших его и взаимно простых с ним чисел:
11, 7, 5, 1.
И след.дроби: 1/12, 5/12, 7/12, 11/12 как раз выполняют все условия определения правильных несократимых дробей:
1. 0 < X < N
2. НОД(X, N) = 1
Поэтому f(12) = 4.
Реализация:
https://gist.github.com/unilecs/be591803618e9cb0b7589a81eaffb844
Тест: