Squares and Cubes (Editorial)

Generate all perfect squares and cubes of positive integers from $1$ to 10^9 and store them in a set $s$. Duplicate values will be automatically eliminated, since a set does not allow duplicates. Then, copy the elements of the set into an array $v$, which will be sorted in ascending order because $s$ is an ordered set.

Next, for each input number $n$, use binary search to determine how many squares and cubes do not exceed $n$. To do this, we use an upper bound search (upper\_bound) — it returns the position of the first element in array $v$ that is strictly greater than $n$. This position is the answer to the query, as it corresponds to the number of qualifying values.

Example

Let's generate all perfect squares and cubes of numbers from $1$ to $100$ (inclusive).

Now process the query for n = 30. In this case, the resulting position is pos = 7, meaning there are exactly $7$ such numbers in the interval from $1$ to $30$.

Note that indexing in the array $v$ starts from zero.

Algorithm implementation

Generate all perfect squares and cubes of positive integers from $1$ to 10^9 and store them in a set $s$. If a number is both a perfect square and a perfect cube (for example, $64$), it will be added to the set only once, since sets automatically eliminate duplicates.

for (i = 1; i * i <= 1000000000; i++)
  s.insert(i * i);
for (i = 1; i * i * i <= 1000000000; i++)
  s.insert(i * i * i);

Then, transfer the elements of the set into an array $v$. Because the set $s$ is ordered, the array $v$ will also be sorted in ascending order.

v = vector<int>(s.begin(), s.end());

Process the given number of tests sequentially.

scanf("%d", &tests);
while (tests--)
{
  scanf("%d", &n);

Using binary search with an upper bound, find the smallest index $pos$ such that all perfect squares and cubes of positive integers not exceeding $n$ are located in the array at positions from $0$ to pos - 1. Thus, the number of listed numbers from $1$ to $n$ equals $pos$.

  res = upper_bound(v.begin(), v.end(), n) - v.begin();
  printf("%d\n", res);
}