Chúng ta cần tìm giá trị số nguyên \(X\) lớn nhất sao cho \(X^2 \le N\). Vì \(N \le 10^{18}\), giá trị của \(X\) sẽ nằm trong khoảng \([0, 10^9]\).

Ta thực hiện tìm kiếm nhị phân trên không gian nghiệm của \(X\) trong đoạn \([0, 10^9]\):

• Đặt lo = 0, hi = 10^9.
• Với mỗi bước, lấy mid = lo + (hi - lo + 1) / 2.
• Kiểm tra điều kiện: nếu mid * mid <= N, thì mid là một nghiệm tiềm năng. Ta thử tìm nghiệm lớn hơn bằng cách gán lo = mid.
• Ngược lại, nếu mid * mid > N, ta gán hi = mid - 1.

Độ phức tạp: \(O(\log(\sqrt{N})) \approx 30\) phép so sánh.

#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long n;
    if (!(cin >> n)) return 0;

    long long lo = 0, hi = 1000000000LL;
    long long ans = 0;
    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        if (mid * mid <= n) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    cout << ans << "\n";
    return 0;
}