Задача 78829
|
|
 |
Условие
Пусть K(x) равно числу таких несократимых дробей a/b, что a < x и b < x (a и b – натуральные числа). Например, K(5/2) = 3 (дроби 1, 2, ½).
Вычислить сумму K(100) + K(100/2) + K(100/3) + ... + K(100/99) + K(100/100).
Решение
Несократимая дробь a/b посчитана в нашей сумме несколько раз. Действительно, она сосчитана по разу во всех K(100/l), где la < 100 и lb < 100. Тем самым получаем, что искомая сумма равна количеству всех дробей a/b (в том числе и сократимых) или, что то же самое, пар (a, b), удовлетворяющих условию 0 < a < 100, 0 < b < 100. Всего таких пар 99². Итак, K(100) + K(100/2) + K(100/3) + ... + K(100/99) + K(100/100) = 99² = 9801.
Ответ
9801.
