На дошці виписано числа A, 2A, 3A, \ldots, тобто -й член дорівнює . Треба знайти найменше натуральне , для якого — повний куб; це і буде відповіддю.
Скористаємось основною теоремою арифметики. Розкладемо на прості множники:
Число є повним кубом тоді й лише тоді, коли всі показники в його розкладі кратні трьом. Тому для кожного простого p_i множник має додати рівно стільки, щоб довести показник до найближчого кратного трьом:
Додавати більше немає сенсу — ми шукаємо мінімальне , — а додавати нові прості множники, яких немає в , тим паче невигідно. Отже,
Реалізація: розкладаємо пробними діленнями до \sqrt{A}, для кожного простого рахуємо показник і домножуємо відповідь на потрібний степінь. Не забудьте про залишок: якщо після циклу не дорівнює одиниці, то це ще один простий множник у першому степені, і він додає до відповіді p^2.
Складність — \mathcal{O}(\sqrt{A}), тобто близько 3 \cdot 10^4 операцій при A \le 10^9.
Перевіримо на прикладі з умови: A = 2 = 2^1, показник , тому f = 2 і n = 2^2 = 4 — четвертий член, тобто 8 = 2^3. Збігається.