Даны натуральное число n и последовательность целых чисел а1, а2,…,аn. Найти количество чисел ai (i=1,2...n), являющихся полными квадратами.

Идея. Число $x$ является полным квадратом ⇔ $x \ge 0$ и $\lfloor\sqrt{x}\rfloor^2 = x$. Отрицательные значения сразу отбрасываем, ноль считается полным квадратом (0 = $0^2$).

Алгоритм.

1. Завести счётчик cnt = 0.

2. Для каждого $a_i$:

   • если $a_i < 0$ → не считаем;

   • иначе найти целую часть квадратного корня $r = \lfloor\sqrt{a_i}\rfloor$;

   • если $r \cdot r = a_i$, увеличить cnt.

3. Вывести cnt.

Сложность: $O(n)$ по времени, $O(1)$ по памяти.

Реализация (Python)

python
Копировать код
import math
n = int(input())
arr = list(map(int, input().split()))
cnt = 0
for x in arr:
    if x >= 0:
        r = math.isqrt(x)          # целочисленный корень без ошибок округления
        if r * r == x:
            cnt += 1
print(cnt)

Реализация (C++, 64-bit)

cpp
Копировать код
#include 
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; 
    if (!(cin >> n)) return 0;
    long long cnt = 0;
    for (int i = 0; i < n; ++i) {
        long long x; cin >> x;
        if (x >= 0) {
            long double sr = sqrtl((long double)x); // корень с запасом по точности
            long long r = (long long)sr;            // пол
            while ((r+1)*(r+1) <= x) ++r;           // страховка от погрешностей
            while (r*r > x) --r;
            if (r*r == x) ++cnt;
        }
    }
    cout << cnt << "\n";
    return 0;
}

Замечания.

• Для очень больших чисел предпочтительнее использовать целочисленный корень (в Python — math.isqrt), чтобы избежать ошибок округления с плавающей запятой.

• Не забывайте, что 0 и 1 — полные квадраты.