Дільники#532

Дільники (Розбір)

Найпростіший спосіб зробити так, щоб одне число ділилося на інше, — зробити їх рівними. Тому базова ідея: відсортувати всі чисел і розбити їх на пари сусідів, піднявши менше число кожної пари до більшого.

Розглянемо два способи розбиття відсортованого масиву 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}). Вартість

S_1 = (a_2 - a_1) + (a_4 - a_3) + \ldots

Спосіб 2: пари (a_2, a_3), (a_4, a_5), \ldots, (a_{2n-2}, a_{2n-1}), а «зайві» крайні числа a_1 і a_{2n} об'єднуємо в останню пару. Тут рівності досягти дорого, зате можна скористатися подільністю: піднімемо a_{2n} до найближчого зверху кратного числа a_1. Це коштує

c = \bigl(-a_{2n}\bigr) \bmod a_1 \;<\; a_1,

і тоді a_1 ділить нове значення. Разом

S_2 = (a_3 - a_2) + (a_5 - a_4) + \ldots + c.

Чому одного з двох завжди досить. Суми «сусідніх різниць» у двох способах разом телескопуються:

S_1 + (S_2 - c) = (a_2 - a_1) + (a_3 - a_2) + \ldots + (a_{2n} - a_{2n-1}) = a_{2n} - a_1.

Оскільки c < a_1, маємо

S_1 + S_2 < a_{2n} - a_1 + a_1 = a_{2n} \le x,

а отже менша з двох сум строго менша за , тобто не перевищує .

Розв'язок: відсортувати числа (запам'ятавши початкові індекси), порахувати обидві вартості, вибрати меншу і вивести відповідне розбиття на пари та самі прирости d_i.

Складність — \mathcal{O}(n \log n) на тест. Не забудьте, що у відповіді треба виводити початкові номери чисел, а не позиції у відсортованому масиві.