Echoes of the Square#12468

Echoes of the Square (Editorial)

Tutorial

The maximum possible value in any query is $R = 1 0^{12}$ . This means the square root of the maximum $R$ is at most $1 0^{6}$ 10^6.

Because $Q$ is up to $1 0^{5}$ 10^5, checking ranges individually for each query is too slow. Instead, we can precompute all valid Echoing Squares globally. We iterate a base integer $i$ from $1$ up to $1 0^{6}$ 10^6, calculate $V = i^{2}$ V = i^2, and verify the four problem conditions. If $V$ satisfies all of them, we append it to a list.

Since we check base integers in increasing order, our list of Echoing Squares will naturally be sorted.

For each of the $Q$ queries, we simply need to count how many values in our precomputed list fall within $[L, R]$ . We can achieve this efficiently using binary search (such as lower_bound and upper_bound in C++). The total count for a query is the difference between the upper bound and lower bound iterators.

Complexity Time Complexity: $O (max R \cdot lo g_{10} (max R))$ \mathcal{O}(\sqrt{\max R} \cdot \log_{10}(\max R)) for the one-time precomputation, and $O (Q lo g K)$ \mathcal{O}(Q \log K) to answer all queries, where $K$ is the total number of valid Echoing Squares found.

Space Complexity: $O (K)$ auxiliary space to store the valid numbers.

1 0^{6}

1 0^{5}

1 0^{6}

V = i^{2}

O (max R \cdot lo g_{10} (max R))

O (Q lo g K)