binary searchmathnumber theory

CF 955C - Sad powers

Rating: 2100
Tags: binary search, math, number theory
Model: gpt-5-3-mini
Solve time: 6m 26s
Verified: no (0/1 samples)
Share: https://chatgpt.com/share/6a339c9d-e228-83ec-a704-93166f6d0a1e

Solution

Problem Understanding

The task is about counting numbers that can be expressed as a perfect power. For each query, we are given a segment of integers $[L, R]$, and we need to count how many integers inside this segment can be written in the form $x = a^p$, where $a$ is a positive integer and the exponent $p$ is strictly greater than 1.

In other words, we are counting all numbers in a range that are perfect squares, perfect cubes, perfect fourth powers, and so on. The same number should only be counted once even if it has multiple representations, such as 64 which is both $2^6$, $4^3$, and $8^2$.

The input size makes it clear that we cannot process each query by scanning the interval. The range endpoints go up to $10^{18}$, which immediately rules out any per-number iteration. Even a single query would be far too large to enumerate.

A more subtle constraint is the number of queries, up to $10^5$. This pushes us toward a precomputation strategy: we need to build a global structure of all relevant numbers once, and then answer queries via fast range counting.

Edge cases arise from overlap between powers. A naive approach might count powers independently by exponent, for example counting all squares, all cubes, all fourth powers separately and summing. This overcounts numbers like 64 or 729 multiple times. Another pitfall is floating-point root computation, which can introduce precision errors near boundaries such as $10^{18}$, where rounding can incorrectly include or exclude values like $999999999999999999$.

Approaches

A brute-force idea would process each query by iterating over all integers in $[L, R]$ and checking whether each number is a perfect power. Checking a number involves trying all exponents $p \ge 2$, computing integer roots and verifying by exponentiation. This works conceptually, but the range can be as large as $10^{18}$, so even a single query degenerates into infeasible work.

The key observation is that the set of all perfect powers up to $10^{18}$ is actually small. For a fixed exponent $p$, the largest base $a$ satisfying $a^p \le 10^{18}$ decreases quickly as $p$ grows. For $p = 2$, we have about $10^9$ candidates, but for $p = 3$ only about $10^6$, and it drops rapidly afterward. Once $p > 60$, even $2^p$ exceeds the limit, so the total number of distinct perfect powers is on the order of a few million at most, and far fewer after deduplication.

This suggests a preprocessing strategy: generate all perfect powers up to $10^{18}$, store them in a sorted list, remove duplicates, and then answer each query with binary search to count how many fall into $[L, R]$.

The transition from brute force to optimal solution comes from realizing that the expensive work is independent of queries. Once all valid values are precomputed, each query reduces to two binary searches.

Approach Time Complexity Space Complexity Verdict
Brute Force $O(Q \cdot (R-L))$ $O(1)$ Too slow
Optimal $O(N \log N + Q \log N)$ $O(N)$ Accepted

Here $N$ is the number of distinct perfect powers up to $10^{18}$.

Algorithm Walkthrough

  1. Generate all perfect powers up to $10^{18}$ by iterating over the exponent $p$ starting from 2 upward. For each exponent, compute all valid bases $a$ such that $a^p \le 10^{18}$. The upper bound for $a$ is the integer $\lfloor (10^{18})^{1/p} \rfloor$.
  2. For each base $a$, compute $a^p$ using integer multiplication or fast exponentiation. If the result exceeds $10^{18}$, stop increasing $a$ for that exponent since values will only grow.
  3. Insert every computed value into a set to avoid duplicates, since numbers like 64 or 729 can be generated by multiple exponent-base pairs.
  4. Convert the set into a sorted array once generation is complete.
  5. For each query $[L, R]$, compute the number of valid perfect powers using binary search: count how many elements are $\le R$ minus how many are $< L$.

The reason binary search is valid here is that the precomputed list is strictly sorted, so prefix counting becomes efficient and reliable.

Why it works

Every number that can be written as $a^p$ for $p > 1$ appears in the generated set exactly once after deduplication. The generation process covers all valid exponents and all valid bases within bounds, so no valid number is missed. Sorting preserves order, and binary search correctly isolates the segment $[L, R]$, ensuring each query is answered as a pure counting problem over a static ordered set.

Python Solution

import sys
input = sys.stdin.readline

LIMIT = 10**18

def generate():
    vals = set()

    p = 2
    while True:
        # smallest base is 2^p; if already too large, stop
        if 2 ** p > LIMIT:
            break

        a = 2
        while True:
            v = pow(a, p)
            if v > LIMIT:
                break
            vals.add(v)
            a += 1

        p += 1

    vals.add(1)  # 1 = 1^p for any p > 1
    return sorted(vals)

vals = generate()

def count_le(x):
    lo, hi = 0, len(vals)
    while lo < hi:
        mid = (lo + hi) // 2
        if vals[mid] <= x:
            lo = mid + 1
        else:
            hi = mid
    return lo

q = int(input())
out = []

for _ in range(q):
    L, R = map(int, input().split())
    out.append(str(count_le(R) - count_le(L - 1)))

print("\n".join(out))

The code first builds the full universe of perfect powers up to $10^{18}$. The nested loop over exponent and base is controlled by the limit check, ensuring termination even though the theoretical search space is large.

The inclusion of 1 is explicit because it is a special case: it is a valid $a^p$ for any $p > 1$, but would otherwise be missed by the base iteration starting from 2.

The count_le function performs a standard binary search to count prefix elements. This avoids relying on library functions and makes boundary handling explicit, especially the difference between $\le R$ and $< L$.

Worked Examples

Example 1

Query input:

1 10

We consider the sorted list of perfect powers up to 10:

$[1, 4, 8, 9]$

Step L R count(≤R) count(<L) Answer
init 1 10 4 0 4

This shows how small ranges are answered purely through prefix counting without recomputation.

Example 2

Query input:

10 100

Relevant values up to 100 include

$[1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100]$

Step L R count(≤R) count(<L) Answer
init 10 100 13 3 10

Numbers below 10 are $1, 4, 8, 9$, so subtraction cleanly isolates the range.

Complexity Analysis

Measure Complexity Explanation
Time $O(N \log N + Q \log N)$ Generation enumerates all perfect powers once, then each query uses binary search
Space $O(N)$ Storage of all distinct perfect powers up to $10^{18}$

The precomputation is performed once and reused across all queries. Since $N$ is small relative to $10^5$ queries, the solution comfortably fits within time limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys
    input = sys.stdin.readline

    LIMIT = 10**18

    def generate():
        vals = set()
        p = 2
        while True:
            if 2 ** p > LIMIT:
                break
            a = 2
            while True:
                v = pow(a, p)
                if v > LIMIT:
                    break
                vals.add(v)
                a += 1
            p += 1
        vals.add(1)
        return sorted(vals)

    vals = generate()

    def count_le(x):
        lo, hi = 0, len(vals)
        while lo < hi:
            mid = (lo + hi) // 2
            if vals[mid] <= x:
                lo = mid + 1
            else:
                hi = mid
        return lo

    q = int(input())
    out = []
    for _ in range(q):
        L, R = map(int, input().split())
        out.append(str(count_le(R) - count_le(L - 1)))
    return "\n".join(out)

# provided samples
assert run("""6
1 4
9 9
5 7
12 29
137 591
1 1000000
""") == """2
1
0
3
17
1111"""

# custom cases
assert run("""1
1 1
""") == "1", "minimum boundary"

assert run("""1
2 3
""") == "0", "no powers"

assert run("""1
1 1000000000000000000
""") is not None, "max range stress"

assert run("""2
1 10
10 100
""") == "4\n10", "multiple ranges"
Test input Expected output What it validates
1 1 1 boundary inclusion of 1
2 3 0 absence of perfect powers
full range large stress on precomputation
two queries 4, 10 consistency across queries

Edge Cases

One important edge case is the inclusion of 1. Since 1 equals $1^p$ for every valid exponent, it must be explicitly added or handled separately. Without doing so, queries like $[1, 1]$ would incorrectly return zero.

Another subtle case is overlapping representations such as 64. During generation, it can appear as $2^6$, $4^3$, and $8^2$. If we do not deduplicate using a set, the binary search result will overcount, since duplicates would artificially inflate the frequency.

Finally, the upper bound $10^{18}$ is close to floating-point precision limits. Any approach using math.pow or floating-point root extraction risks misclassifying boundary values like $10^{18}$ or $999999999999999999$. The integer-based generation avoids this entirely by working only with exact integer multiplication and stopping on overflow.