Majestic Numbers (Editorial)

Solution

Observations:

• Any number divisible by x^a can be written as y = k \cdot x^a for some integer k \ge 1.

• To maximize majesticness, we want the largest $a$ such that there exists some y = k \cdot x^a in the range [l,r].

• Once $a$ is fixed, the largest possible y \le r is y = \left\lfloor \frac{r}{x^a} \right\rfloor \cdot x^a.

Algorithm:

1. Iterate over powers of $x$: x^0, x^1, x^2, \dots until x^a > r.

2. For each power p = x^a, compute the largest multiple that's smaller than $r$:

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

3. If y \ge l, update the answer.

Complexity: Each test case performs at most \log_x r iterations, so the total complexity is \mathcal{O}(t \cdot \log r).

#include <bits/stdc++.h>
#define ll long long

using namespace std;

void solve()
{
    ll l , r , x;
    cin >> l >> r >> x;
    ll ans = r;
    ll y = x;
    while(y<=r)
    {
        ll rr = (r/y)*y;
        if(rr>=l)
            ans = (r/y)*y;
        y*=x;
    }
    cout << ans << "\n";
}

int main()
{
    ll T=1;
    cin >> T;
    while(T--)
        solve();
}