Majestic Numbers (Həll təhlili)

Həll

Müşahidələr:

• x^a-ya bölünən hər bir ədəd y = k \cdot x^a şəklində yazıla bilər, burada k \ge 1 tam ədəddir.

• Majesticness-i maksimum etmək üçün elə ən böyük $a$ tapmaq lazımdır ki, [l,r] aralığında y = k \cdot x^a formasında bir ədəd mövcud olsun.

• $a$ sabit olduqda, y \le r üçün ən böyük mümkün qiymət:

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

Alqoritm:

1. $x$-in qüvvətləri üzrə iterasiya et: x^0, x^1, x^2, \dots ta ki x^a > r olsun.

2. Hər p = x^a üçün $r$-dən böyük olmayan ən böyük qatını hesabla:

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

3. Əgər y \ge l isə, cavabı yenilə.

Mürəkkəblik: Hər test üçün maksimum \log_x r iterasiya edilir, ümumi mürəkkəblik \mathcal{O}(t \cdot \log r).