Квадрати і куби (Розбір)

Згенеруємо всі квадрати і куби натуральних чисел від $1$ до 10^9 і збережемо їх у множину $s$. Повторювані числа автоматично виключаються, оскільки множина не допускає дублікатів. Потім скопіюємо елементи множини в масив $v$, який вже буде відсортований за зростанням, тому що $s$ — впорядкована множина.

Далі для кожного вхідного числа $n$ за допомогою бінарного пошуку визначимо кількість квадратів і кубів, що не перевищують $n$. Для цього використовуємо пошук за верхньою межею (upper\_bound) — він поверне позицію першого елемента в масиві $v$, строго більшого $n$. Ця позиція і буде відповіддю на запит, оскільки вона відповідає кількості підходящих чисел.

Приклад

Згенеруємо квадрати і куби чисел від $1$ до $100$ включно.

Виконаємо запит для n = 30. У цьому випадку знайдена позиція буде рівна pos = 7, тобто в інтервалі від $1$ до $30$ містяться рівно $7$ підходящих чисел. Нагадаємо, що індексація в масиві $v$ починається з нуля.

Реалізація алгоритму

Згенеруємо всі квадрати і куби натуральних чисел від $1$ до 10^9 і збережемо їх у множину $s$. Якщо число одночасно є квадратом і кубом (наприклад, $64$), воно буде додане в множину лише один раз, оскільки множини автоматично виключають повтори.

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

Потім перенесемо елементи множини в масив $v$. Оскільки множина $s$ впорядкована, масив $v$ також буде відсортований за зростанням.

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

Послідовно обробляємо $tests$ тестів.

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

За допомогою бінарного пошуку за верхньою межею знаходимо найменший індекс $pos$ такий, що всі квадрати і куби натуральних чисел, не перевищуючі $n$, знаходяться в масиві на позиціях від $0$ до pos - 1. Таким чином, кількість виписаних чисел від $1$ до $n$ дорівнює $pos$.

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