Задача 6 из 11

Сумма делителей

Время 2 с · память 256 МБ

Пусть RR — сумма всех различных натуральных делителей целого числа. Например, для числа 12 имеем R=1+2+3+4+6+12=28R = 1 + 2 + 3 + 4 + 6 + 12 = 28.

Напишите программу, которая перебирает целые числа, большие AA, в порядке возрастания и ищет среди них такие, для которых значение RR оканчивается на цифру 6.

Входные данные

Во входных данных содержится одно натуральное число AA (A≤109A \le 10^9). Искомые пять чисел существуют при любом допустимом значении AA.

Выходные данные

Выведите первые пять найденных чисел в порядке возрастания, каждое в отдельной строке: сначала само число, затем соответствующее ему значение RR.

Примеры

Ввод 1
500000
Вывод 1
500032 1070356
500035 606816
500039 501456
500050 949716
500052 1333696
Ввод 2
1
Вывод 2
5 6
22 36
28 56
39 56
42 96

Примечание

В первом примере первое найденное число 500032=26⋅13⋅601500032 = 2^6 \cdot 13 \cdot 601. Его различные делители имеют вид 2i⋅13j⋅601k2^i \cdot 13^j \cdot 601^k, где 0≤i≤60 \le i \le 6, а jj и kk равны 0 или 1. Поэтому их сумма равна (1+2+4+8+16+32+64)(1+13)(1+601)=1070356(1 + 2 + 4 + 8 + 16 + 32 + 64)(1 + 13)(1 + 601) = 1070356. При дальнейшем переборе подходят 500035, 500039, 500050 и 500052 с суммами делителей 606816, 501456, 949716 и 1333696 соответственно. Все эти суммы оканчиваются на 6.

Во втором примере первое найденное число — 5: его делители 1 и 5 дают в сумме 6.

Решение
Загрузка редактора…
Результат появится здесь

Черновик сохраняется в этом браузере.

Ошибка в задаче