Sashko-Array Constructor (Editorial)

Якщо x \le d, відповідь очевидна: масив з одного елемента $[x]$.

Інакше треба розбити $x$ на множники, кожен з яких не перевищує $d$, і зробити це якнайменшою кількістю множників.

Спочатку перевіримо, чи розв'язок узагалі існує. Розкладемо $x$ на прості множники. Якщо серед них є простий p > d, то жоден множник добутку не зможе його «сховати» — будь-який елемент масиву, кратний $p$, буде не меншим за p > d. У цьому разі виводимо $-1$.

Якщо ж усі прості не перевищують $d$, розв'язок існує, і будувати його вигідно жадібно: щоразу відщипувати від залишку якомога більший множник.

Формально: доки поточне значення $y$ більше за $d$, шукаємо найбільший дільник $y$, що не перевищує $d$, додаємо його до відповіді й ділимо $y$ на нього. Коли $y$ стає не більшим за $d$, додаємо його останнім елементом.

Кожен крок зменшує $y$ щонайменше вдвічі (бо взятий дільник не менший за $2$), тому кроків буде щонайбільше близько $30$ при x \le 10^9 — це з великим запасом вкладається в обмеження n \le 1000 з умови.

Дільники зручно шукати одним проходом до \sqrt{x}: для кожного $i$, що ділить $x$, кандидатами є і $i$, і $x/i$; серед тих, що не перевищують $d$, беремо найбільший.

Оскільки x \le 10^9, розклад пробними діленнями коштує близько 3 \cdot 10^4 операцій.