07/04/2025 06:42:21

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1842. ABC-гипотеза

Ограничения: время – 3s/6s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В августе 2012 года японский математик Синити Мотидзуки опубликовал доказательство знаменитой ABC-гипотезы, которая была сформулирована в работах Массера и Эстерле в 80-х гг. XX века. Эта гипотеза оказалась весьма полезной при получении множество фундаментальных результатов теории чисел и алгебраической геометрии и, в частности, великая теорема Ферма может быть выведена в несколько строк как её следствие.

Для этой задачи необходимо понятие радикала. Радикалом числа

$"rad"(n)$ называется произведение всех простых множителей этого числа. Например,

$"rad"(24)=2*3=6$ . У этого числа есть несколько очевидных свойств. Например, если

$a$ и

$b$ взаимно просты, то есть не имеют общих делителей, отличных от единицы, то

$"rad"("ab")\ =\ "rad"(a)*"rad"(b)$ . Кроме этого, равенство

$"rad"(a)=a$ выполняется тогда и только тогда, когда

$a$ – произведение попарно различных простых чисел.

Рассмотрим тройки чисел

$(a,\ b,\ c)$ , для которых

$a+b=c$ и все три числа взаимно просты. Так как числа

$a$ ,

$b$ ,

$c$ взаимно просты, то

$"rad"("abc")="rad"(a)*"rad"(b)*"rad"(c)$ . Массера и Эстерле заинтересовал вопрос: какое из чисел

$c$ или

$"rad"("abc")$ больше? Оказалось, что однозначного ответа на этот вопрос нет. Например, для тройки

$(2,\ 3,\ 5)$

$"rad"(2*3*5)=2*3*5=30>5$ , а для тройки

$(1,\ 8,\ 9)$

$"rad"(1*8*9)="rad"(23*32)=2*3=6<9$ .

Дальнейшие исследования позволили установить, что тройки первого типа встречаются намного чаще: если взять случайную тройку, то почти всегда будет выполняться именно первое неравенство. Поэтому тройки, для которых

$c>"rad"("abc")$ , получили название исключительных. Удалось доказать, что таких троек бесконечно много, и даже построить бесконечную серию троек, у которой отношение

$"rad"("abc")/c$ стремится к 0.

Математикам удалось найти другое ограничение на возможные значения радикала, которое получило название "ABC-гипотеза": для любого действительного числа

$r>1$ существует конечное число троек натуральных чисел

$(a,\ b,\ c)$ таких, что для них выполняются одновременно три условия:

$a+b=c$ ;

$a$ ,

$b$ и

$c$ взаимно просты и

$c>"rad"("abc")^r$ .

Напишите программу для поиска исключительных троек, которая для заданного

$c$ находит все пары натуральных чисел

$(a,\ b)$ , таких что

$a<b$ ,

$a+b=c$ , числа

$a$ ,

$b$ и

$c$ взаимно просты (достаточно проверить взаимную простоту любой пары из этой тройки) и

$"rad"("abc")<c$ .

Формат ввода

Первая строка ввода содержит натуральное число

$c$ (

$2\ ≤\ c\ ≤\ 10^7$ ).

Формат вывода

В первой строке вывести число

$K$ – количество найденных пар. Затем вывести

$K$ строк – найденные пары в порядке возрастания

$a$ .

Пример ввода

Пример вывода

1
1 8