`*` Những số có số lượng ước lẻ là số chính phương. (Tính chất này mình không tiện chứng minh).

Vậy việc đơn giản của ta là đếm số lượng số chính phương từ `1 -> n`. Ta có thể kiểm tra bằng cách lấy `sqrt n`, làm tròn và bình phương lên xem có đúng bằng n hay không.

Nhưng việc đó chỉ khả thi với `n <= 10^7 ~ 10^8`. 

Vậy giải quyết bằng cách nào?

Nhận thấy số chính phương sẽ có dạng bình phương của 1 số nguyên dương. 

Hay nếu `A` là số chính phương thì tồn tại số nguyên dương `X` thoã mãn sao cho: `X * X = A`.

Đến đây, việc cần làm của ta là đếm số lượng số nguyên dương `X` thoã mãn `X * X <= n`

Hay `X <= sqrt n`. Đáp án là `floor(sqrt(n))` (Làm tròn xuống)

$\texttt{C++}$

#include <bits/stdc++.h>

using namespace std;

int main()
{
    freopen("SULE.inp", "r", stdin);
    freopen("SULE.out", "w", stdout);
    long long n;
    cin >> n;
    long long k = sqrt(n);
    cout << k;   
    return 0;
}