Majestic Numbers (Розбір)

Розв’язок

Спостереження:

• Будь-яке число, кратне x^a, можна записати як y = k \cdot x^a, де k \ge 1 — ціле число.

• Щоб максимізувати majesticness, потрібно знайти найбільше $a$, для якого існує y = k \cdot x^a у відрізку [l,r].

• При фіксованому $a$ найбільше можливе y \le r:

  y = \left\lfloor \frac{r}{x^a} \right\rfloor \cdot x^a

Алгоритм:

1. Перебрати степені $x$: x^0, x^1, x^2, \dots поки x^a > r.

2. Для кожного p = x^a знайти найбільше кратне, не більше за $r$:

   y = \left\lfloor \frac{r}{p} \right\rfloor \cdot p

3. Якщо y \ge l, оновити відповідь.

Складність: для кожного тесту виконується не більше ніж \log_x r ітерацій, отже загальна складність \mathcal{O}(t \cdot \log r).