Задача
Дробь $\frac{m}{n}\ $ называется правильной несократимой, если [latex] 0 < m < n [/latex] и [latex] НОД (m, n) = 1.[/latex] Найдите количество правильных несократимых дробей со знаменателем $n$.
Входные данные
Каждая строка является отдельным тестом и содержит число $n$ ([latex]n < 10^9 [/latex]). Последняя строка содержит $0$ и не обрабатывается. Количество тестов не больше $100.$
Выходные данные
Для каждого $n$ в отдельной строке вывести ответ на поставленную задачу.
Тесты
| Вход | Выход |
| 12 123456 7654321 0 |
4 41088 7251444 |
| 552 99693 34 991 8863 0 |
176 56160 16 990 8862 |
| 1 5754 99291 7752 3321 0 |
1 1632 63272 2304 2160 |
| 99291 581293 3215788 1224262 68291 692110 0 |
63272 581292 1422720 565032 66792 272448 |
| 3 12 64 877 0 |
2 4 32 876 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <iostream> using namespace std; int main () { int n, k; while (cin >> n and n!=0) { k = n; for (int i = 2; i*i <= n; i++) { if (n % i == 0) { while (n % i == 0) { n/= i; } k-=k/i; } } if (n > 1) { k-=k/n; } cout << k << endl; } return 0; } |
Решение
Вводим поток чисел до тех пор пока не встретим $0$ и проводим над каждым числом следующую операцию.
Вычисляем количество правильных несократимых дробей с помощью функции Эйлера. Занимаемся проверкой числа на простоту. Простой, но медленный метод проверки простоты заданного числа $n$ известен как перебор делителей. Будем проверять, является ли $n$ кратным каждому целому числу от $2$ до $\sqrt{n}$.
В ходе проверки на простоту находим и другие кратные делители, если таковые имеются. При обнаружение какого то кратного найдем количество несократимым для данного несократимого. Частное, где числитель — это наше число, а знаменатель — определенный кратный делитель, будет количеством сократимых чисел, связанное с текущим кратным делителем. Естественно, если отнимем всё число от делимого, то получим число несократимых.
Повторяем цикл пока обнаруживаются новые кратные нашему числу и с каждым разом уменьшая количество несократимых.