Козак Вус і НСД#134

Козак Вус і НСД (Розбір)

Задача розпадається на дві незалежні частини, і головне — побачити, що їх справді можна розділити.

Частина 1: зробити масив неспадним. Оскільки числа дозволено лише збільшувати, мінімальний неспадний масив, що домінує над вихідним, будується жадібно зліва направо:

a'_i = \max(a_i,\ a'_{i-1}).

Сумарна вартість цього кроку — \sum (a'_i - a_i), і меншою вона бути не може: кожне a'_i — це нижня межа, нав'язана умовою.

Частина 2: зробити НСД більшим за одиницю. Якщо \gcd > 1, то в нього є простий дільник , і всі числа кратні . Навпаки, кратність усіх чисел одному простому вже гарантує \gcd \ge p > 1. Тому достатньо перебрати прості (складені перевіряти не треба — вони лише дорожчі).

Для фіксованого найдешевше підняти кожне число до найближчого зверху кратного:

\mathrm{cost}(p) = \sum_i \left(\left\lceil \frac{a'_i}{p} \right\rceil p - a'_i\right).

І ось чому дві частини не конфліктують: округлення вгору — монотонна операція, тому з a'_i \le a'_{i+1} випливає \lceil a'_i/p \rceil p \le \lceil a'_{i+1}/p \rceil p. Отже, після округлення масив залишається неспадним, і сумарна вартість — це просто сума вартостей обох частин.

Відповідь — вартість першої частини плюс \min_p \mathrm{cost}(p) по всіх простих p \le \max a'_i.

Прості знаходимо решетом Ератосфена один раз на початку. Оцінка: простих до 10^4 приблизно , тому повний перебір коштує близько 1229 \cdot n операцій на тест. Прискорити допомагає рання зупинка: щойно поточна сума перевищила найкращу знайдену, перебір для цього можна припинити. Корисно також одразу взяти p = 2 як початкову межу — вона дає вартість не більшу за .