Задача розпадається на дві незалежні частини, і головне — побачити, що їх справді можна розділити.
Частина 1: зробити масив неспадним. Оскільки числа дозволено лише збільшувати, мінімальний неспадний масив, що домінує над вихідним, будується жадібно зліва направо:
Сумарна вартість цього кроку — \sum (a'_i - a_i), і меншою вона бути не може: кожне a'_i — це нижня межа, нав'язана умовою.
Частина 2: зробити НСД більшим за одиницю. Якщо \gcd > 1, то в нього є простий дільник , і всі числа кратні . Навпаки, кратність усіх чисел одному простому вже гарантує \gcd \ge p > 1. Тому достатньо перебрати прості (складені перевіряти не треба — вони лише дорожчі).
Для фіксованого найдешевше підняти кожне число до найближчого зверху кратного:
І ось чому дві частини не конфліктують: округлення вгору — монотонна операція, тому з 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 як початкову межу — вона дає вартість не більшу за .