I. Giới thiệu Về Bài Toán Kiểm Tra Số Chính Phương

Bài toán xác định một số nguyên không âm có phải là số chính phương hay không đã trở thành một phần quen thuộc trong lập trình. Số chính phương được định nghĩa là số tự nhiên n khi và chỉ khi tồn tại một số tự nhiên x sao cho x² = n. Các số chính phương điển hình như 0 (0 = 0²), 1 (1 = 1²), 4 (4 = 2²), 9 (9 = 3²), 16 (16 = 4²) và 25 (25 = 5²),...

Đây là một bài toán cơ bản nhưng khi giới hạn n tăng lên, ví dụ lên đến 100 chữ số, việc kiểm tra số chính phương trở nên khó khăn hơn. Bài viết này sẽ giới thiệu các phương pháp kiểm tra số chính phương, bắt đầu từ phương pháp đơn giản đến phương pháp xác suất.

II. Các Phương Pháp Kiểm Tra Số Chính Phương

1. Phương Pháp Ngây Thơ

Phương pháp đầu tiên là duyệt qua tất cả các số tự nhiên x không lớn hơn √n và kiểm tra xem x² có bằng n hay không. Độ phức tạp của phương pháp này là O(√n), có thể thực hiện tốt với n ≤ 10^9.

2. Phương Pháp Kiểm Tra Căn Bậc Hai

Phương pháp thứ hai đơn giản hơn và hiệu quả hơn là kiểm tra xem căn bậc hai của n là số nguyên hay không. Nếu x = ⌊√n⌋, chỉ cần kiểm tra x * x = n. Phương pháp này có độ phức tạp O(1) và có thể áp dụng với n ≤ 10^{18}.

3. Phương Pháp Tìm Kiếm Nhị Phân

Đối với các số lớn hơn giới hạn của kiểu dữ liệu long long trong C++, ta phải sử dụng phương pháp tìm kiếm nhị phân để tìm x sao cho x² = n. Tuy nhiên, độ phức tạp của phương pháp này tương đối cao do cần xử lý số lớn dưới dạng chuỗi.

III. Phương Pháp Kiểm Tra Số Chính Phương Bằng Xác Suất

Dưới đây là lý thuyết nền tảng cho phương pháp này:

Nếu n là số chính phương, chữ số hàng đơn vị của n chỉ có thể thuộc các giá trị 0, 1, 4, 5, 6, 9.
Một số được gọi là giả chính phương nếu nó không phải là số chính phương nhưng vẫn qua được hàm kiểm tra chữ số hàng đơn vị.

Bằng cách sử dụng hàm kiểm tra chứa số dư của n với module khác nhau, ta có thể giảm xác suất n là giả chính phương xuống mức rất thấp. Hệ thống kiểm tra sử dụng 20 lần gọi hàm kiểm tra với các số ngẫu nhiên sẽ đem lại kết quả chính xác cao.

Cài Đặt Giải Thuật

Dưới đây là cài đặt tiếng C++ cho thuật toán kiểm tra số chính phương:

cpp Copy

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

int get_remainder(string &n, int p) {
    int r = 0;
    for (char digit: n) r = (r * 10 + (digit - '0')) % p;
    return r;
}

int g(string &n, int p) {
    int remainder = get_remainder(n, p);
    for (int i = 0; i <= p / 2 + 1; ++i)
        if (i * i % p == remainder) return 1;
    return 0;
}

string is_squared_number(string &n, int k) {
    for (int i = 1; i <= k; ++i) {
        int p = 50000 + (1LL * rand() * rand() % 50000);
        if (!g(n, p)) return n + " is not a squared number";
    }
    return n + " is a squared number";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    srand(time(NULL));
    cout << is_squared_number("4", 20) << endl;
    cout << is_squared_number("10", 20) << endl;
    return 0;
}

IV. Kết Luận

Phương pháp xác suất đem lại giải pháp đơn giản và hiệu quả cho việc kiểm tra số chính phương, đặc biệt là khi làm việc với các số lớn. Dù có độ chính xác không tuyệt đối, nhưng với xác suất sai rất thấp, phương pháp này hoàn toàn phù hợp cho các cuộc thi lập trình. Chúng tôi khuyến khích các độc giả áp dụng phương pháp này trong các bài toán thực tiễn.

V. Tài Liệu Tham Khảo

Phương pháp kiểm tra số chính phương bằng xác suất.
Competitive Programming 3 - Steven Halim & Felix Halim.
source: viblo

Phương Pháp Kiểm Tra Số Chính Phương Bằng Xác Suất: Giải Pháp Đơn Giản Cho Số Lớn