Задача
“Название задачи можно напевать на мотив марша или строевой песни…”
Сколько существует правильных несократимых дробей на промежутке [[latex]0[/latex]..[latex]1[/latex]], знаменатель которых не превышает [latex]n[/latex]?
Входные данные
Натуральное число [latex]n[/latex] ([latex]n < 10001[/latex]).
Выходные данные
Вывести количество правильных несократимых дробей на промежутке [[latex]0..1[/latex]], знаменатель которых не превышает [latex]n[/latex].
Тесты
| Входные данные | Выходные данные |
|---|---|
| 1 | 0 |
| 10000 | 30397485 |
| 5 | 9 |
| 80 | 1965 |
| 37 | 431 |
| 5168 | 8119803 |
| 9973 | 30237929 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include <iostream> using namespace std; int euler_f (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; } int main() { int n; cin >> n; int sum = 0; for (int i = 2; i <= n; ++i) { sum += euler_f(i); } cout << sum; return 0; } |
Решение задачи
Для решения данной задачи вопользуемся функцией Эйлера [latex] \varphi (n)[/latex], равной количеству натуральных чисел, меньших [latex]n[/latex] и взаимно простых с ним. Очевидно, что количество правильных несократимых дробей со знаменателем [latex]n[/latex] равно [latex] \varphi (n)[/latex]. И тогда количество правильных дробей со знаменателем, не превыщающим [latex]n[/latex] равно [latex] \sum\limits_{i=2}^{n}{\varphi (n)}[/latex] (тут мы учли, что при [latex]i[/latex] = 1 знаменатель дроби равен 1 и дробь не будет правильной).
Ссылки
Условие задачи на сайте E-Olymp
код задачи на Ideone
описание функции Эйлера на Wikipedia