Сашко-Конструктор масивів#7

Сашко-Конструктор масивів (Розбір)

Автор задачі:

Ціцей Павло

Задачу підготував:

Фейса Богдан

Розбір написав:

Олександр Тимкович

Якщо максимальний простий дільник більший за то відповідь . Це так, тому що щоб отримати добуток рівний , всі його прості дільники повинні бути використані.

Щоб знайти масив мінімальної довжини, можна слідувати такому жадібному алгоритму:

  • якщо число рівне то закінчити роботу.

  • нехай це максимальний дільник який не більший за . Записати в масив число та розділити на .

Знаходити дільник можна зі складністю O(\sqrt{x}).