Задача 7 из 11

Делитель с окончанием 11

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

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

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

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

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

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

Примеры

Ввод 1
1350050
Вывод 1
1350051 311
1350055 270011
1350062 511
1350063 40911
1350066 225011
Ввод 2
221
Вывод 2
222 111
333 111
422 211
444 111
555 111

Примечание

В первом примере 1350051=311⋅43411350051 = 311 \cdot 4341, 1350055=270011⋅51350055 = 270011 \cdot 5, 1350062=511⋅26421350062 = 511 \cdot 2642, 1350063=40911⋅331350063 = 40911 \cdot 33 и 1350066=225011⋅61350066 = 225011 \cdot 6. В каждом разложении первый множитель — минимальный допустимый делитель: он оканчивается на 11 и не равен ни 11, ни самому числу. У остальных чисел между границей 1350050 и последним найденным числом подходящих делителей нет.

Во втором примере первое найденное число — 222: его делитель 111 оканчивается на 11, а делитель 11 использовать нельзя. Искомый делитель может быть больше квадратного корня из числа.

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

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

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

Делитель с окончанием 11 — задание 25 ЕГЭ по информатике