Найпростіший спосіб зробити так, щоб одне число ділилося на інше, — зробити їх рівними. Тому базова ідея: відсортувати всі чисел і розбити їх на пари сусідів, піднявши менше число кожної пари до більшого.
Розглянемо два способи розбиття відсортованого масиву a_1 \le a_2 \le \ldots \le a_{2n}.
Спосіб 1: пари (a_1, a_2), (a_3, a_4), \ldots, (a_{2n-1}, a_{2n}). Вартість
Спосіб 2: пари (a_2, a_3), (a_4, a_5), \ldots, (a_{2n-2}, a_{2n-1}), а «зайві» крайні числа a_1 і a_{2n} об'єднуємо в останню пару. Тут рівності досягти дорого, зате можна скористатися подільністю: піднімемо a_{2n} до найближчого зверху кратного числа a_1. Це коштує
і тоді a_1 ділить нове значення. Разом
Чому одного з двох завжди досить. Суми «сусідніх різниць» у двох способах разом телескопуються:
Оскільки c < a_1, маємо
а отже менша з двох сум строго менша за , тобто не перевищує .
Розв'язок: відсортувати числа (запам'ятавши початкові індекси), порахувати обидві вартості, вибрати меншу і вивести відповідне розбиття на пари та самі прирости d_i.
Складність — \mathcal{O}(n \log n) на тест. Не забудьте, що у відповіді треба виводити початкові номери чисел, а не позиції у відсортованому масиві.