Для каждого натуpального числа a, чеpез m(a) обозначим мощность множества {HОД(x¹², x+a) ¦ x in N}.
Решить в натуральных числах уравнение: m(a) = a

Решение

Приведу решение в изложении Олега Полубасова.
____________________________________________________________________
Пусть y = x+a,
тогда HОД(x¹², x+a) = HОД((y-a)¹², y) = HОД(a¹², y). {HОД(a¹², y), y in N, y > a} равно количеству делителей числа a¹².
Пусть а = П_i=1ⁿ {p_i^d_i} - разложение а на степени простых,
тогда количество делителей числа a¹² m(a) = П_i=1ⁿ (12*d_i+1).
Hадо решить уравнение m(a) = а.
Так как m(a) == 1 (mod 12), то ни m(a), ни а не делятся ни на 2, ни на 3.
Пусть b_i = (p_i^d_i)/(12*d_i+1),
тогда 1 = а/m(a) = П_i=1ⁿ b_i. Только при p из {5, 7, 11} сомножители могут быть меньше единицы, при этом их произведение = (5*7*11)/13³ > 1/6, так что все остальные b_i должны быть меньше 6, то есть:
1. если d_i = 1, то p_i < 6*13 = 78.
2. если d_i = 2, то p_i < (6*25)^1/2 < 13.
3. если d_i = 3, то p_i < (6*37)^1/3 < 7.
4. если d_i = 4, то p_i < (6*49)^1/4 < 5.
Таким образом, d_i не превышают 3, а значит m(a) может содержать множители только 13, 5 и 37, причём 13 и 37 - только по одному разу, а 5 - не более 3 раз (но чётное число раз). Следовательно, множитель 5 может содержаться 0 или 2 раза, значит 37 тоже исключается. 13 может содержаться 0 или 1 раз.
Из 5² и 13 можно составить 4 произведения, и каждое из них удовлетворяет ответу.
Проверяем:
a = 1, m(a) = 1.
а = 13, m(a) = 12+1 = 13.
а = 25 = 5², m(a) = 12*2+1 = 25.
а = 325 = 13*5², m(a) = (12+1)*(12*2+1) = 325.
Ответ: {1, 13, 25, 325}
____________________________________________________________________

Обсуждение

Ясно, что задача №49 объединяет в себе две разные задачи. Каждая допускает вполне естественные обобщения. Обобшение первой подзадачи я зарезервирую для будущих задач.

Что же касается второй подзадачи, то для ее обсуждения и обобщения я вновь предоставлю слово Олегу Полубасову.
____________________________________________________________________
Пусть а = П_i=1ⁿ {p_i_i^d_i} -- разложение а на степени простых. N(a) = n -- количество простых делителей а без учёта кратности.
S(a) = ΣП_i=1ⁿ d_i -- количество простых делителей а с учётом кратности (сумма показателей).
M(a) = П_i=1ⁿ {d_i+1} -- количество всех натуральных делителей а . z -- параметр задачи.
m(a,z) = M(a^z) = П_i=1ⁿ {z*d_i+1}.
Когда z понятно из контекста, можно писать просто m(a).
Нас интересуют решения в натуральных числах уравнения m(a,z) = a.
Легко видеть, что m(a) - мультипликативная (но не вполне мультипликативная) функция, то есть m(a*b) = m(a)*m(b), если a и b взаимно просты.

У меня нет законченного исследования, я буду просто проводить рассуждения, иллюстрируя их примерами.

Возникает очень интересный цикл:
1. Зная число а, можно найти его разложение на степени простых.
2. Зная степени простых (даже потеряв информацию об основаниях),
можно (простой заменой) построить набор z*d_i+1
3. Перемножив все z*d_i+1, можно получить m(a).
4. Приравняв a = m(a), перейдём к пункту 1.

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

Пример 1. Применение отсечений в задаче m(a,11).
Так как m(a,11) = а, а m(p^d) может быть меньше p^d только при p \in {2, 3, 5, 7}, то 2^d/(11*d+1) < 12³/(3*5*7), откуда d < 11, а сумма степеней < 11+3=14.
Это довольно плохая оценка, не учитывающая специфики задачи, но стартовать можно и с неё.
(11*0+1) = 1
(11*1+1) = 12 = 2²*3
(11*2+1) = 23
(11*3+1) = 34 = 2*17
(11*4+1) = 45 = 3²*5
(11*5+1) = 56 = 2³*7
(11*6+1) = 67
(11*7+1) = 78 = 2²*3*13
(11*8+1) = 89
(11*9+1) = 100 = 2²*5²
(11*10+1) = 111 = 3*37
Следовательно p \in {2, 3, 5, 7, 13, 17, 23, 37, 67, 89}.
Пусть dS(p^d) = S(m(p^d))-d -- увеличение суммы степеней.
Составим табличку. В заголовке матрицы - возможные основания, столбец d - возможные степени, столбец S - веса строк, столбец dS - увеличение суммы степеней, в матрице (назовём её А) - разложение m(p^d) на простые.
--+-------------------------------+---+---
_d| _2 _3 23 17 _5 _7 67 13 89 37 | S | dS
--+-------------------------------+---+---
_1| _2 _1 -- -- -- -- -- -- -- -- | 3 | +2
_2| -- -- _1 -- -- -- -- -- -- -- | 1 | -1
_3| _1 -- -- _1 -- -- -- -- -- -- | 2 | -1
_4| -- _2 -- -- _1 -- -- -- -- -- | 3 | -1
_5| _3 -- -- -- -- _1 -- -- -- -- | 4 | -1
_6| -- -- -- -- -- -- _1 -- -- -- | 1 | -5
_7| _1 _1 -- -- -- -- -- _1 -- -- | 4 | -4
_8| -- -- -- -- -- -- -- -- _1 -- | 1 | -7
_9| _2 -- -- -- _2 -- -- -- -- -- | 4 | -5
10| -- _1 -- -- -- -- -- -- -- _1 | 2 | -8
--+-------------------------------+---+---
Решение задачи состоит в том, чтобы выбрать какие-то строки (не обязательно по одному разу), и, просуммировав их, получить строку, содержащую в качестве значений номера выбранных строк и именно в выбранном количестве.
Первая операция легко алгебраизуется (это просто умножение целочисленного вектора-строки на матрицу), а как формализовать интерпретацию ответа, я не знаю. о суть должна быть понятна.
В поиске нужного мультимножества строк может помочь столбец dS, так как сумма dS должна оказаться равной нулю (в m(a) должны входить те же множители и в тех же количествах, что и в а).
Имеется только одна строка с положительным dS, и она должна войти в решение, так как только из отрицательных dS нуля не составить.
Если взять строку 1 три раза, то потребуются три столбца с 1, а их можно получить, минимум, из трёх разных строк, так как ни в одной строке нет двух единиц в столбцах, не пересекающихся с первой строкой.
Для того чтобы сумма номеров взятых строк не превысила 13, это должны быть строки 2, 3 и 4 или 2, 3 и 5. о сумма весов этих строк превышает 13. Значит строка 1 берётся не более двух раз. Тогда строки с dS <= -4 можно исключить из таблицы.
-+-------------------+---+---
d| _2 _3 23 17 _5 _7 | S | dS
-+-------------------+---+---
1| _2 _1 -- -- -- -- | 3 | +2
2| -- -- _1 -- -- -- | 1 | -1
3| _1 -- -- _1 -- -- | 2 | -1
4| -- _2 -- -- _1 -- | 3 | -1
5| _3 -- -- -- -- _1 | 4 | -1
-+-------------------+---+---
2*2-1-1-1-1=0,
первая строка уже даёт 2⁴, если взять ещё и пятую, то степень двойки станет больше 5, значит пятая строка исключается.
Если взять третью строку, то степень двойки станет больше 4, значит третья строка исключается. Остаются вторая и четвёртая, но две первых степени из них набрать невозможно.
2-1-1=0,
обе -1 - из одной строки, значит из второй. Всё!
Ответ:
m(1,11) = 1.
m(12*23*23,11) = m(3*2²*23²,11) = 12*23*23.

Для z=11 решение оказалось довольно длинным, но вот для z=p-1, где p-простое, всё обычно отсекается гораздо проще. Во-первых, m(p,p-1) = p-1+1 = p.
Во-вторых, в столбце с именем p больше нет ни одной единицы (следующий неноль встретился бы только в p+1-й строке), что позволяет использовать первую строку для уравновешивания других сумм.
В-третьих, z делится, как минимум, на 2, а то и на другие простые, что сильно сокращает число строк.

Пример 2. Применение отсечений в задаче m(a,12).
Это именно та задача, которая была в конкурсе.
12 = 2²*3, то есть а не делится ни на 2, ни на 3, наименьший простой делитель - 5.
Строим табличку.
-+-------+---+---
d| 13 _5 | S | dS
-+-------+---+---
1| _1 -- | 1 | 0
2| -- _2 | 2 | 0
-+-------+---+---
Для всех последующих степеней dS отрицательны, так как уже m(5³) = 12*3+1 = 37 < 125 = 5³.
А так как ни одного положительного dS нет, то степени с отрицательным dS можно не рассматривать.
Ответ:
m(1,12) = 1.
m(13,12) = 13.
m(5²,12) = 25 = 5².
m(13*5²,12) = 13*25 = 13*5².

Пример 3. Применение отсечений в задаче m(a,990).
990 = 2*3²*5*11, то есть а не делится ни на 2, ни на 3, ни на 5, наименьший простой делитель - 7.
-+--------------------------+---+---
d| 991 __7 283 2971 _17 233 | S | dS
-+--------------------------+---+---
1| __1 --- --- ---- --- --- | 1 | _0
2| --- __1 __1 ---- --- --- | 2 | _0
3| --- --- --- ___1 --- --- | 1 | -2
4| --- --- --- ---- __1 __1 | 2 | -2
-+--------------------------+---+---
Для всех последующих степеней dS отрицательны, так как уже m(7⁵) = 990*5+1 = 4951 < 16807 = 7⁵.
А так как ни одного положительного dS нет, то степени с отрицательным dS можно не рассматривать.
Hо вторая строка не является решением. Для того, чтобы получить решение, к ней надо прибавить удвоенную первую.
Ответ:
m(1,990) = 1.
m(991,990) = 991.
m(7*283*991²,990) = 991*991*7*283.
____________________________________________________________________

Награды

С задачей №49 успешно справились Дмитрий Милосердов, Алекскей Ковальский, Андрей Винокуров, Владислав Франк и Олег Полубасов. Верное решение, но без строго обоснования его полноты, дал Андрей Богданов.
Кроме того, Олег Полубасов и Андрей Винокуров рассмотрели ряд обобщений задачи. В итоге: Олег Полубасов (он продвинулся по пути обобщений дальше Андрея Винокурова) получает 6 призовых балллов; Андрей Винокуров - 5 призовых баллов; Дмитрий Милосердов, Алексей Ковальский и Влад Франк - по 4 призовых балла; Андрей Богданов - 2 призовых балла.

Эстетитеская оценка задачи - 2.5 балла