Kvadratlar və kuublar (Həll təhlili)

1-dən 10^9-ə qədər bütün təbii ədədlərin kvadratlarını və kublarını yaradıb $s$ çoxluğunda saxlayacağıq. Təkrarlanan ədədlər avtomatik olaraq istisna edilir, çünki çoxluq təkrara icazə vermir. Sonra çoxluğun elementlərini $v$ massivinə kopyalayacağıq ki, bu da artıq artan sırada sıralanmış olacaq, çünki $s$ — sıralanmış çoxluqdur.

Daha sonra hər bir giriş ədədi $n$ üçün ikili axtarış vasitəsilə $n$-dən çox olmayan kvadratlar və kubların sayını təyin edəcəyik. Bunun üçün yuxarı sərhədə (upper\_bound) görə axtarışdan istifadə edəcəyik — bu $v$ massivində $n$-dən ciddi şəkildə böyük olan ilk elementi göstərəcək. Bu mövqe sorğunun cavabı olacaq, çünki bu uyğun nömrələrin sayına uyğundur.

Misal

$1$-dən $100$-ə qədər (daxil olmaqla) ədədlərin kvadratlarını və kublarını yaradacağıq.

Sorğunu n = 30 üçün icra edək. Bu halda tapılan mövqe pos = 7 olacaq, yəni $1$-dən $30$-a qədər olan aralıqda dəqiq olaraq $7$ uyğun ədəd var. Yadda saxlayaq ki, $v$ massivində indeksləmə sıfırdan başlayır.

Əlgoritmin həyata keçirilməsi

1-dən 10^9-ə qədər bütün təbii ədədlərin kvadratlarını və kublarını yaradıb $s$ çoxluğunda saxlayacağıq. Əgər ədəd eyni zamanda həm kvadrat, həm də kubdursa (məsələn, $64$), bu yalnız bir dəfə çoxluğa əlavə ediləcək, çünki çoxluqlar təkrarlamaları avtomatik olaraq aradan qaldırır.

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

Sonra çoxluğun elementlərini $v$ massivinə köçürəcəyik. Çünki $s$ çoxluğu sıralanmışdır, $v$ massivi də artan sıra ilə sıralanacaq.

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

Ardıcıl olaraq $tests$ testlərini işləyəcəyik.

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

Yuxarı sərhədə görə ikili axtarış vasitəsilə kiçik $pos$ indeksini tapırıq ki, $n$-dən çox olmayan bütün təbii ədədlərin kvadratları və kubları $0$-dan pos - 1-ə qədər mövqelərdə yerləşir. Bu şəkildə $1$-dən $n$-ə qədər olan ədədlərin sayı $pos$ ilə eynidir.

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