Теория чисел на Росатоме

Из основной теоремы арифметики следует, что и двух чисел можно рассматривать как взятие соответственно максимума и минимума по степеням простых множителей в этих двух числах. Пусть — степени соответствующих простых в числе . Пусть — степени соответствующих простых в числе .

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

Для поиска наименьшей суммы приведём два способа:

Первый способ.

Из основной теоремы арифметики следует, что . По неравенству о средних при фиксированном произведении чисел их сумма тем больше, чем больше одно число отличается от другого (сумма вида , производная которой равна возрастает при ). Поэтому нам нужно найти максимально близкое значение к корню из этого произведения. это общий НОД, так что остаётся составить из имеющихся множителей ближайшее к число.

Второй способ.

Просто сделаем полный перебор для этих восьми пар, чтобы быстро посчитать и забрать свои баллы за задачу

Осталось выбрать наименьшую сумму и выписать ответ.