Решение задачи 446

Условие:

Через p(n,k) обозначим количество делителей числа n, не меньших k. Найдите p(1001,1)+...+p(2000,1000).

Решение:

Рассмотрим натуральное число s, такое что 1≤s≤2000. Посмотрим в какие из p(,) оно может дать вклад. Это число может дать только в p(1000+n,n), где n≤s. Рассмотрим числа 1001, 1002, ..., 1000+s. Нетрудно видеть, что они дают все разные остатки при делении на s, значит, ровно одно делится на s. Отсюда следует, что найдется единственная p(,), в которую даст вклад число s.

Вышесказанное верно для любого 1≤s≤2000. Значит, сумма p(1001,1)+...+p(2000,1000) равна 2000.

Ответ: 2000.