Tìm kiếm nhị phân phần nguyên căn bậc hai
Trong hệ thống tính toán số học chính xác cao của AI Empire Academy, cần tính phần nguyên căn bậc hai $⌊ √(x)
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: binary search basics, integer arithmetic.
Nội dung đề bài
Mục tiêu kiến thức
- Nắm vững tư duy Tìm kiếm nhị phân trên không gian nghiệm (Binary Search on Answer).
- Xử lý các số nguyên cực lớn lên đến 1018 trong thời gian O(log x) mà không bị sai số dấu phẩy động.
- Kiểm tra hợp lệ dữ liệu âm và ném ngoại lệ
ValueError.
Mô tả bài toán
Trong hệ thống tính toán số học chính xác cao của AI Empire Academy, cần tính phần nguyên căn bậc hai ⌊ √(x) floor của một số nguyên không âm x.
Quy định nghiêm ngặt:
- Nghiêm cấm sử dụng các hàm tính căn bậc hai có sẵn như
math.sqrt,math.isqrt, hoặc toán tử lũy thừa số thựcx ** 0.5. Bạn phải tự cài đặt thuật toán Tìm kiếm nhị phân trên không gian nghiệm để tìm số nguyên lớn nhất m sao cho:
m2 ≤ x
- Nếu x < 0, hàm phải ném ra ngoại lệ
ValueError("Khong the tinh can bac hai so am").
Hãy viết hàm integer_sqrt(x: int) -> int trả về phần nguyên căn bậc hai của x.
Input
Một số nguyên x (int).
Output
Số nguyên int là ⌊ √(x) floor.
Ràng buộc
- -106 ≤ x ≤ 1018.
- Thời gian chạy tối đa: 1000ms.
- Giới hạn bộ nhớ: 256MB.
Ví dụ 1
Input
`x = 8`Output
`2`Giải thích
√(8) ≈ 2.8284, phần nguyên là 2 (22 = 4 ≤ 8, trong khi 32 = 9 > 8).
Ví dụ 2
Input
`x = 16`Output
`4`Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.