Мінімальна подільна послідовність#12966

Мінімальна подільна послідовність (Розбір)

Для чисел є лише одне можливе значення для a_i, яке є множником , це число . Це означає, що в масиві повинні бути всі числа від \lfloor \frac{n}{2} \rfloor + 1 до . Таким чином масив матиме щонайменше \lceil \frac{n}{2} \rceil елементів.

Для кожного числа k \le \frac{n}{2} можна знайти число в інтервалі [\lfloor \frac{n}{2} \rfloor + 1, n], яке ділиться на . Це випливає з того що розмір проміжку більший або рівний за . Враховуючи вищесказане, масив з елементів від \lfloor \frac{n}{2} \rfloor + 1 до є мінімальним можливим масивом, що задовольняє усі умови задачі.

Складність .