I. Nhắc lại bài toán kiểm tra số chính phương

Bài toán kiểm tra số chính phương là một bài toán vô cùng quen thuộc, có thể nói là ở mức độ "nhập môn" dành cho tất cả những bạn học lập trình. Nhắc lại về số chính phương, ta có khái niệm:

Số tự nhiên $n$ được gọi là số chính phương khi và chỉ khi tồn tại số tự nhiên $x$ sao cho: $x^2 = n$.

Một vài số chính phương có thể kể đến như $0 = 0^2, 16 = 4^2$ hay $81 = 9^2, \dots$

Bài toán đặt ra là kiểm tra một số nguyên không âm $n$ cho trước có phải là số chính phương hay không? Nếu như $n$ là số chính phương thì in ra $1,$ ngược lại in ra $0$.

Thông thường, giới hạn $n$ sẽ được cho trong khoảng $10^{18}$ đổ lại, nghĩa là vẫn nằm trong khả năng lưu trữ của các kiểu dữ liệu nguyên thủy ở ngôn ngữ C++. Khi đó việc kiểm tra số chính phương khá đơn giản. Tuy nhiên, điều gì xảy ra khi giới hạn của $n$ được đẩy lên cao hơn, chẳng hạn như khoảng $100$ chữ số?

Để trả lời câu hỏi trên, trước hết chúng ta sẽ cùng xem xét lại một số phương pháp kiểm tra số chính phương thường được sử dụng!

1. Phương pháp "ngây thơ"

Cách làm đơn giản nhất đó là duyệt qua toàn bộ các số tự nhiên $x$ không vượt quá $\sqrt{n}$ và kiểm tra xem $x^2$ có bằng $n$ hay không? Cách làm này có độ phức tạp là $O(\sqrt{n}),$ có thể đáp ứng yêu cầu về thời gian chạy nếu như $n \le 10^9$.

Cài đặt

int is_squared_number(int n)
{
    for (int x = 0; x * x <= n; ++x)
        if (x * x == n)
            return 1;
	
    return 0;
}

2. Phương pháp kiểm tra căn bậc hai

Một cách làm đơn giản hơn và tối ưu hơn, đó là kiểm tra xem căn bậc hai của $n$ có phải là một số tự nhiên hay không. Nếu như gọi $x = \lfloor{\sqrt{n}}\rfloor,$ thì chỉ cần kiểm tra $x \times x$ có bằng với $n$ không là biết được đáp án.

Cách làm này chỉ tốn độ phức tạp $O(1)$ với các giá trị số trong khoảng lưu trữ của các kiểu dữ liệu nguyên thủy, và có thể đáp ứng cho giới hạn $n \le 10^{18}$.

Cài đặt

int is_squared_number(long long n)
{
    long long x = sqrt(n);
    return x * x == n;
}

3. Phương pháp tìm kiếm nhị phân

Đối với các giá trị $n$ "lớn" (ngoài vùng lưu trữ của kiểu dữ liệu long long trong C++), việc tìm trực tiếp căn bậc hai của $n$ bằng hàm sqrt là không khả thi. Khi đó, nếu như các bạn không sử dụng các ngôn ngữ có khả năng xử lý số lớn mạnh mẽ như Python hay Java, thì ta sẽ phải code lại hàm sqrt, đồng thời dùng kiểu chuỗi kí tự để lưu trữ giá trị của $n$.

Một cách làm khả thi đó là tìm kiếm nhị phân giá trị $x$ thỏa mãn $x^2 = n$. Bởi vì ta biết rằng, nếu như $n$ là số chính phương thì chỉ tồn tại duy nhất một giá trị $x$ như vậy.

Sơ đồ thuật toán có thể mô tả như sau:

int is_squared_number(string &n)
{
    string l = "0", r = n;
    while (l <= r)
    {
        string mid = (l + r) / 2;
        
        if (mid * mid == n)
            return 1;
        else if (mid * mid < n)
            l = mid + 1;
        else 
            r = mid - 1;
    }
	
    return 0;
}

Tuy nhiên, vấn đề ở đây là khoảng giá trị của căn bậc hai của $n$ có thể rất lớn, vì thế ta sẽ phải đặt toàn bộ các giá trị $l, r$ là chuỗi kí tự và tiến hành nạp chồng toán tử để xử lý số lớn với các phép toán: +, -, *, / , <, <=, == (các bạn xem lại cách xử lý số lớn tại đây). Điều này khiến cho code sẽ cực kì dài, và dĩ nhiên xử lý số lớn thì sẽ kéo theo độ phức tạp tính toán sẽ vô cùng lớn. Vì thế, đây không hẳn là một cách làm hay, mặc dù nó vẫn cho ra được kết quả mong muốn.

Vậy giải pháp tốt nhất là gì?

II. Thuật toán random kiểm tra số chính phương

1. Các lý thuyết nền tảng

Trước khi đi vào cài đặt cụ thể của thuật toán kiểm tra số chính phương bằng phương pháp xác suất (hay còn gọi là thuật toán random), chúng ta sẽ cùng nghiên cứu một vài lý thuyết số học nền tảng.

Kí hiệu $a \text{ mod } b$ là số dư của phép chia $a$ cho $b$.

Nhận xét 1

Nếu như $n$ là số chính phương thì chữ số hàng đơn vị của $n$ chỉ có thể thuộc tập $S = \{0, 1, 4, 5, 6, 9\}$.

Chứng minh

Ta có các chữ số hàng đơn vị của mọi số khi bình phương lên đều phải là một trong các chữ số tận cùng của giá trị: $1^1 = 1, 2^2 = 4, 3^3 = 9, 4^4 = 16, 5^5 = 25, 6^6 = 36, 7^7 = 49, 8^8 = 64, 9^9 = 81$.

Do đó các số chính phương cũng chỉ có thể có có chữ số tận cùng thuộc tập $S = \{0, 1, 4, 5, 6, 9\}$.

Hệ quả 1

Một số nếu như có chữ số tận cùng thuộc tập $S$ thì nó có khả năng là số chính phương. Ta tạm gọi một hàm $f(x)$ là hàm kiểm tra $x$ có khả năng là số chính phương hay không. Nếu như chữ số tận cùng của $x$ thuộc tập $S$ thì $f(x) = \text{true},$ ngược lại $f(x) = \text{false}$.

Định nghĩa 1

Một số được gọi là số giả chính phương nếu như nó không phải là số chính phương, nhưng vẫn vượt qua được hàm kiểm tra $f$. Nghĩa là số $n$ được gọi là số giả chính phương nếu nó không phải là số chính phương nhưng $f(n) = \text{true}$.

Ta có thể thấy, nếu như chỉ sử dụng hàm $f$ để kiểm tra một số có phải số chính phương không, thì trong một đoạn $[l, r]$ đủ lớn, sẽ có khoảng $60\%$ các số là số giả chính phương (bởi vì xét một số tự nhiên $n$ thì có $60\%$ khả năng $n \text{ mod } 10 \in S$). Vậy nếu như ta tăng thêm số lượng hàm kiểm tra sử dụng lên, hoặc đổi sang một hàm kiểm tra khác thì có thể giảm xác suất một số là số giả chính phương đi hay không? Điều này hoàn toàn khả thi, và thực tế là xác suất đó sẽ giảm đi theo cơ số $2$ khi ta tăng số lượng phép kiểm tra lên (sau đây sẽ chứng minh).

Nhận xét 2

Gọi $S(p)$ là tập hợp các số dư khác nhau của mọi số chính phương khi chia cho giá trị $p,$ tức là:

$$S(p) = \{i^2 \text{ mod } i \ | \ i \in \mathbb{N} \}$$

Khi đó, nếu gọi $|S(p)|$ là số lượng phần tử của tập $S(p)$ thì $|S(p)| \le \left\lfloor{\frac{p}{2}}\right\rfloor + 1$

Chứng minh

Xét hai giá trị $p$ và $x$ bất kì, ta luôn luôn có:

$$x^2 \equiv (p - x)^2 \ (\text{mod } p)$$

Thật vậy, ta có:

$$(p - x)^2 \equiv (p^2 + x^2 - 2px)^2 \equiv x^2 \ (\text{mod } p)$$

Suy ra:

$$0^2 \equiv p^2 \ (\text{mod } p)$$

$$1^2 \equiv (p - 1)^2 \ (\text{mod } p)$$

$$2^2 \equiv (p - 2)^2 \ (\text{mod } p)$$

$$...$$

Từ đây ta kết luận được số lượng phần tử của tập $S$ không thể vượt quá $\left\lfloor{\frac{p}{2}}\right\rfloor + 1,$ điều phải chứng minh!

Định nghĩa 2

Ta định nghĩa một hàm $g(n, p)$ là một hàm số thỏa mãn:

$$g(n, p) = \begin{cases}1;& \text{nếu } n \in S(p). \\ 0;& \text{ngược lại.}\end{cases}$$

Thay vì sử dụng hàm $f,$ giờ chúng ta sẽ sử dụng hàm $g$ để kiểm tra xem một số $n$ có phải là số chính phương hay không. Lúc này, số giả chính phương sẽ là số mà không phải số chính phương nhưng vẫn cho ra kết quả $g(n, p) = 1$ với một modulo $p$ nào đó.

Dựa vào nhận xét $2,$ ta sẽ thấy khi giá trị modulo $p$ đủ lớn thì có khoảng $50\%$ khả năng một số $n$ sẽ có $g(n, p) = 1$. Như vậy, nếu chỉ dùng duy nhất một hàm $g$ để kiểm tra, thì xác suất một số là số giả chính phương sẽ là $50\%$. Nếu như ta sử dụng nhiều lần hàm $g(n, p)$ với các giá trị $p$ mỗi lần là khác nhau để kiểm tra một số có là số chính phương không thì sao?

Mã giả dưới đây mô tả thuật toán sử dụng $20$ lần hàm $g$ với $20$ giá trị $p$ khác nhau cho một số $n$ bất kì:

// Hàm trả về 1 nếu n là số chính phương, ngược lại trả về 0.
is_squared_number(n):
    for i = 1 to 20:
        // Chọn ngẫu nhiên một giá trị p, giả sử luôn khác các giá trị trước.
        p = random();

        // Nếu n % 10 không thuộc S(p) thì n không phải số chính phương.
        if g(n, p) == 0:
            return 0;
			
    // Nếu sau 20 lần thử mà n % 10 vẫn thuộc S(p) với cả 20 giá trị p
    // thì khả năng cao n là số chính phương.
    return 1;

Hàm số kiểm tra trên sẽ chỉ sai khi $n$ là một số giả chính phương. Và ta có thể tính toán được xác suất $n$ là số giả chính phương sẽ càng ngày càng nhỏ đi khi tăng số lần kiểm tra lên. Tôi sẽ trình bày cách tính xác suất đó ngay sau đây!

Gọi $p_i$ là modulo được tạo ra random ở lần thử thứ $i,$ và $P(p_i, n)$ là xác suất để một số tự nhiên $n$ là số giả chính phương với phép thử theo modulo $p$. Ta có:

$$P(p_i, n) = \frac{|S(p)|}{p_i} \le \frac{\left\lfloor{\frac{p_i}{2}}\right\rfloor + 1}{p_i} \le \frac{1}{2} + \frac{1}{p_i}$$

Khi $p_i$ càng lớn thì $\frac{1}{p_i}$ sẽ càng nhỏ, nên có thể xem như nó tiến tới $0$ khi $p_i$ đủ lớn. Như vậy, xác suất một số tự nhiên là số giả chính phương là xấp xỉ $50\%$ nếu như chỉ sử dụng hàm $g$ để kiểm tra $1$ lần. Vậy nếu như các lần kiểm tra là độc lập, thì mỗi khi sử dụng thêm $1$ lần hàm kiểm tra $g,$ với modulo khác các lần trước, xác suất một số là số giả chính phương sẽ giảm đi một nửa, nghĩa là còn $25\%$ ở lần thử thứ $2, 12.5\%$ ở lần thứ $3, \dots$

Tất nhiên, điều này chỉ xảy ra khi các lần kiểm tra là độc lập, chẳng hạn như các giá trị $p_i$ được chọn ở mỗi lần là đôi một nguyên tố cùng nhau. Tuy nhiên, đối với phạm vi các kì thi lập trình thì ta không cần tính chính xác cao đến vậy, nên có thể tạm bỏ qua tính độc lập của các lần kiểm tra.

Vậy có thể nói một cách đại khái rằng, sau $k$ lần test, thì xác suất một số là số giả chính phương sẽ bằng: $\frac{1}{2^k} = \frac{1}{2^{20}} \approx 9 \times 10^{-7}$ - có thể xem như là xác suất sai của thuật toán kiểm tra. Với xác suất nhỏ như vậy, thì trong các bài toán lập trình thi đấu, việc ra kết quả sai gần như là không bao giờ xảy ra. Dĩ nhiên, nếu cẩn thận hơn nữa thì các bạn chỉ cần tăng thêm số lần kiểm tra lên, khoảng $50$ lần chẳng hạn.

2. Cài đặt giải thuật

Dưới đây tôi sẽ cài đặt mẫu giải thuật kiểm tra số chính phương bằng phương pháp xác suất, ngôn ngữ sử dụng là C++.

#include <bits/stdc++.h>

using namespace std;

// Số dư của phép chia số n cho số p.
int get_remainder(string &n, int p)
{
    int r = 0;
    for (char digit: n)
        r = (r * 10 + (digit - '0')) % p;
		
    return r;
}

// Kiểm tra một lần xem g(n, p) có bằng 1 hay không.
int g(string &n, int p)
{
    int remainder = get_remainder(n, p);

    // Nếu số dư n % p thuộc tập S(p) thì trả về 1, ngược lại trả về 0.
    for (int i = 0; i <= p / 2 + 1; ++i)
        if (i * i % p == remainder)
            return 1;
			
    return 0;
}

string is_prime_number(string &n, int k)
{
    for (int i = 1; i <= k; ++i)  
    {
        // Tạo random số p trong đoạn [50000, 99999].
        int p = 50000 + (1LL * rand() * rand() % 50000);
	    
        if (!g(n, p))
            return n + " is not a squared number";
    }
	
    return n + " is a squared number";
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    srand(time(NULL));
	
    // Thử kiểm tra với một vài số tự nhiên khác nhau.
    // 2^2.
    cout << is_prime_number("4", 20) << endl;
    // 3^2 + 1.
    cout << is_prime_number("10", 20) << endl;
    // 123456789123456789^2.
    cout << is_prime_number("15241578780673678515622620750190521", 20) << endl;
    // 123456789123456789^2 + 1.
    cout << is_prime_number("15241578780673678515622620750190522", 20) << endl;
	
    return 0;
}

Kết quả chạy đoạn code trên sẽ là:

4 is a squared number
10 is not a squared number
15241578780673678515622620750190521 is a squared number
15241578780673678515622620750190522 is not a squared number

3. Kết luận

Như vậy, chúng ta vừa thảo luận về phương pháp kiểm tra một số có phải là số chính phương không khi số đó rất lớn. Có thể thấy, nếu như không có công cụ bignum, thì việc kiểm tra sẽ cực kì khó khăn, nhưng không phải là không có phương pháp đơn giản hơn.

Đối với phương pháp xác suất, chúng ta chấp nhận đánh đổi tính chính xác tuyệt đối của giải thuật để đổi lấy sự đơn giản trong cài đặt cũng như giảm độ phức tạp thuật toán. Tuy nhiên, gần giống với giải thuật Rolling Hash, tỉ lệ sai của giải thuật trên là vô cùng nhỏ, nên đối với các cuộc thi lập trình không cần phải lo ngại.

Tuy nhiên, nếu như đối với các bài tập dạng ACM và có multi - testcases thì tỉ lệ bạn bị sai vẫn có thể xảy ra nếu như người chấm bài đọc được solution của bạn và cố tình tạo ra test hiểm để hack code của bạn, nhưng trên thực tế điều này rất hiếm khi xảy ra, có chăng là ở kì thi cấp quốc tế mà thôi! Vì vậy các bạn đừng ngần ngại sử dụng cách làm này thay cho phương pháp sử dụng bignum cực kì phức tạp.

III. 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.