Lời giải: Căn bậc hai

Ý tưởng

Khác với căn bậc hai số nguyên chia đôi khoảng, bài này cần tính trên số thực. Ta vẫn áp dụng ý tưởng "thu hẹp khoảng mỗi bước một nửa" nhưng với biến liên tục:

• Bắt đầu với \(lo = 0\), \(hi = \max(1, N)\).
• Ở mỗi bước, \(mid = (lo + hi)/2\).
  • Nếu \(mid^2 \ge N\): \(hi = mid\).
  • Ngược lại: \(lo = mid\).

Sau \(K\) bước, khoảng \([lo, hi]\) có độ dài \(hi - lo \le \frac{hi_0}{2^K}\). Với \(N \le 10^{18}\) và \(K = 200\), sai số \(\le 10^{-42}\), nhỏ hơn nhiều so với yêu cầu \(10^{-6}\).

Cạm bẫy

• Vì phải dùng số thực, hãy dùng long double (\(\ge 80\) bit) để có độ chính xác cao.
• In ra với fixed và setprecision(10).

Độ phức tạp

• Thời gian: \(O(\log(precision))\) - chạy vòng lặp cố định ~\(200\) lần.
• Bộ nhớ: \(O(1)\).

Mã nguồn tham khảo

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long double N;
    cin >> N;
    if (N < 0) N = -N;
    if (N == 0) {
        cout << fixed << setprecision(10) << 0.0L << "\n";
        return 0;
    }
    long double lo = 0.0L, hi = max((long double)1.0L, N);
    for (int it = 0; it < 200; it++) {
        long double mid = lo + (hi - lo) / 2;
        if (mid * mid >= N) hi = mid;
        else lo = mid;
    }
    cout << fixed << setprecision(10) << (lo + hi) / 2 << "\n";
    return 0;
}