CF 104637D - Squares and Cubes

We are asked to count how many integers in the range from 1 to n can be written in at least one of two special forms: a perfect square or a perfect cube. If a number can be written both ways, it should still be counted only once.

codeforcescompetitive-programming

CF 104637D - Squares and Cubes

Rating: -
Tags: -
Solve time: 59s
Verified: yes

Solution

Problem Understanding

We are asked to count how many integers in the range from 1 to n can be written in at least one of two special forms: a perfect square or a perfect cube. If a number can be written both ways, it should still be counted only once.

So for each query n, we are essentially counting the size of the union of two sets: all numbers of the form i² and all numbers of the form j³, restricted to being at most n.

The input size is small in terms of number of test cases, at most 20, but the value of n is large, up to 10⁹. This immediately rules out any approach that iterates through all integers up to n. A linear scan per test case would require up to 10⁹ operations, which is far beyond what fits in one second.

A more subtle constraint implication is that the answer itself is driven by integer powers. Both squares and cubes grow quickly, so their counts up to n are about n^(1/2) and n^(1/3), which are at most around 31623 and 1000 respectively when n is 10⁹. This suggests that iterating over roots is viable.

A naive mistake is to double count numbers that are both square and cube. For example, 64 is both 8² and 4³, so it appears in both sequences. Any approach that simply adds the number of squares and cubes will overcount such numbers.

A second subtle edge case is the smallest values. At n = 1, both square and cube sequences include 1, but it should still contribute only once.

Approaches

A brute-force interpretation would be to iterate over every integer x from 1 to n and check whether it is a perfect square or perfect cube. Checking whether x is a square or cube requires computing integer roots and verifying them, which is O(1) per check. This leads to O(n) per test case, which at n = 10⁹ is about a billion checks per query, far too slow even before considering multiple test cases.

The key structural observation is that we do not need to examine each integer, only the generators of squares and cubes. Every square is generated by some integer i with i² ≤ n, and every cube is generated by some integer j with j³ ≤ n. That reduces the problem to counting valid indices i and j, which is about sqrt(n) and cbrt(n).

However, simply computing sqrt(n) + cbrt(n) overcounts numbers that are both squares and cubes. A number is both a square and a cube exactly when it is a sixth power, since lcm(2,3) = 6. So numbers of the form k⁶ appear in both lists and must be subtracted once.

This turns the problem into a classic inclusion-exclusion count over power sets: count squares, count cubes, subtract sixth powers.

Approach Time Complexity Space Complexity Verdict
Brute Force O(n) per test O(1) Too slow
Optimal O(1) per test O(1) Accepted

Algorithm Walkthrough

Optimal counting via powers

  1. For a given n, compute how many integers i satisfy i² ≤ n. This is equivalent to floor(sqrt(n)). This counts all squares up to n.
  2. Compute how many integers j satisfy j³ ≤ n, which is floor(cbrt(n)). This counts all cubes up to n.
  3. Compute how many integers k satisfy k⁶ ≤ n, which is floor(n^(1/6)). This counts numbers that are both squares and cubes, since those are exactly sixth powers.
  4. Add the counts of squares and cubes, then subtract the sixth powers count. This removes duplicates that were counted in both the square and cube sets.
  5. Output the resulting value for each test case.

The reason each step works is that we are not iterating over numbers directly, but over their unique generating exponents, and each transformation is monotone in the generator variable.

Why it works

Every integer x ≤ n that is a square has a unique representation x = i² for some integer i, and similarly every cube has a unique representation x = j³. This creates two injective mappings from integers i and j into the set of valid numbers. The only overlap occurs when a number can be written simultaneously as i² and j³, which implies x is a perfect sixth power. Since sixth powers are counted once in each set, subtracting their count corrects the overcount exactly once per overlapping element. No other overlaps exist because exponent representations are unique in prime factorization terms.

Python Solution

import sys
input = sys.stdin.readline

def isqrt(n: int) -> int:
    lo, hi = 0, 10**9
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= n:
            lo = mid + 1
        else:
            hi = mid - 1
    return hi

def icbrt(n: int) -> int:
    lo, hi = 0, 10**6
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid * mid <= n:
            lo = mid + 1
        else:
            hi = mid - 1
    return hi

def i6th(n: int) -> int:
    lo, hi = 0, 10**3
    while lo <= hi:
        mid = (lo + hi) // 2
        p = mid * mid
        p = p * p * p
        if p <= n:
            lo = mid + 1
        else:
            hi = mid - 1
    return hi

def solve():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = isqrt(n)
        b = icbrt(n)
        c = i6th(n)
        print(a + b - c)

if __name__ == "__main__":
    solve()

The implementation separates the three counting tasks into integer root computations. Each helper function uses binary search rather than floating point operations, avoiding precision issues at large boundaries like 10⁹.

The square root function searches up to 10⁹ since sqrt(10⁹) is about 31623, safely within range. The cube root search space is capped at 10⁶, which is already far above cbrt(10⁹) ≈ 1000. The sixth root is capped at 10³ because (10³)⁶ = 10¹⁸, which comfortably exceeds all possible inputs.

The final formula directly applies inclusion-exclusion without storing any intermediate sets.

Worked Examples

Example 1: n = 10

We compute squares, cubes, and sixth powers.

Step Value
floor(sqrt(10)) 3 (1, 4, 9)
floor(cbrt(10)) 2 (1, 8)
floor(n^(1/6)) 1 (1)
result 3 + 2 - 1 = 4

The result confirms that 1, 4, 8, and 9 are counted once each.

Example 2: n = 100

Step Value
floor(sqrt(100)) 10
floor(cbrt(100)) 4
floor(n^(1/6)) 2
result 10 + 4 - 2 = 12

This includes all squares up to 100, all cubes up to 100, with sixth powers removed from double counting.

These traces show that the overlap correction consistently removes exactly those numbers that appear in both sequences.

Complexity Analysis

Measure Complexity Explanation
Time O(log n) per test Each root is computed via binary search over a fixed range
Space O(1) Only a few variables are used per test

The constraints allow up to 20 test cases, so the total work is negligible. Even with binary search overhead, the solution is effectively constant time per query.

Test Cases

import sys, io

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

    def isqrt(n: int) -> int:
        lo, hi = 0, 10**9
        while lo <= hi:
            mid = (lo + hi) // 2
            if mid * mid <= n:
                lo = mid + 1
            else:
                hi = mid - 1
        return hi

    def icbrt(n: int) -> int:
        lo, hi = 0, 10**6
        while lo <= hi:
            mid = (lo + hi) // 2
            if mid * mid * mid <= n:
                lo = mid + 1
            else:
                hi = mid - 1
        return hi

    def i6th(n: int) -> int:
        lo, hi = 0, 10**3
        while lo <= hi:
            mid = (lo + hi) // 2
            p = mid * mid
            p = p * p * p
            if p <= n:
                lo = mid + 1
            else:
                hi = mid - 1
        return hi

    def solve():
        t = int(input())
        out = []
        for _ in range(t):
            n = int(input())
            a = isqrt(n)
            b = icbrt(n)
            c = i6th(n)
            out.append(str(a + b - c))
        return "\n".join(out)

    return solve()

assert run("""6
10
1
25
1000000000
999999999
500000000
""") == """4
1
6
32591
32590
23125"""
Test input Expected output What it validates
n = 1 1 smallest overlap case
n = 10⁹ large value upper bound correctness
mixed tests varying outputs consistency across roots

Edge Cases

For n = 1, both square and cube counts equal 1, and the sixth power count is also 1. The formula produces 1 + 1 − 1 = 1, correctly avoiding double counting.

For n = 10⁹, square root is 31622, cube root is 1000, and sixth root is 10. The subtraction ensures the 10 sixth powers are not counted twice. The algorithm handles this purely through integer root computation without overflow or precision issues.