Lý Thuyết Số & Số Nguyên Tố

1. Bản chất vấn đề & trực giác thuật toán (the core problem & intuition)

Trong khoa học máy tính và lập trình thi đấu, các bài toán xoay quanh ước số, bội số và số nguyên tố là nền tảng của mật mã học (như thuật toán mã hóa khóa công khai RSA), phân tích độ phức tạp thuật toán và tối ưu hóa tài nguyên.

Vấn đề 1: Tìm ước chung lớn nhất (GCD)

Cho hai số nguyên dương $A$ và $B$. Ước chung lớn nhất $\gcd(A, B)$ là số nguyên dương lớn nhất đồng thời chia hết cả $A$ và $B$.

• Cách ngây thơ: Thử tất cả các số từ $\min(A, B)$ giảm dần về $1 \implies \mathcal{O}(\min(A, B))$. Khi $A, B \approx 10^{18}$, cách này hoàn toàn bất khả thi.
• Định lý Euclid: $\gcd(A, B) = \gcd(B, A \pmod B)$.
• Mỗi bước lấy dư $A \pmod B$, giá trị giảm ít nhất một nửa sau mỗi 2 bước lặp $\implies$ Thuật toán dừng lại sau tối đa $\mathcal{O}(\log(\min(A, B)))$ bước (khoảng $\le 60$ phép tính với số $10^{18}$).

Vấn đề 2: Kiểm tra số nguyên tố & phân tích thừa số nguyên tố

Một số nguyên $N > 1$ là số nguyên tố nếu nó chỉ có đúng 2 ước là $1$ và chính nó.

• Tính chất đối xứng của ước số: Nếu $d$ là ước của $N$ thì $\frac{N}{d}$ cũng là ước của $N$.
• Bất biến $\sqrt{N}$: Nếu $N$ là hợp số, nó bắt buộc phải có ít nhất một ước nguyên tố $p \le \sqrt{N}$. Do đó, ta chỉ cần duyệt kiểm tra các số từ $2$ đến $\lfloor \sqrt{N} \rfloor$ trong $\mathcal{O}(\sqrt{N})$ thay vì $\mathcal{O}(N)$.

2. Mô phỏng từng bước (visual step-by-step simulation)

Ví dụ 1: Mô phỏng thuật toán euclid tìm $\gcd(252, 105)$

Ví dụ 2: Mô phỏng sàng Eratosthenes tìm các số nguyên tố $\le 20$

1. Khởi tạo mảng đánh dấu isPrime từ $2 \dots 20$ đều là true.
2. Xét $i = 2$ (nguyên tố) $\implies$ Gạch bỏ các bội $4, 6, 8, 10, 12, 14, 16, 18, 20$.
3. Xét $i = 3$ (nguyên tố) $\implies$ Gạch bỏ các bội $9, 12, 15, 18$ (bắt đầu gạch từ $i^2 = 9$).
4. Xét $i = 4$ (đã bị gạch) $\implies$ Bỏ qua.
5. Vì $i^2 = 5^2 = 25 > 20$, vòng lặp dừng lại.

Danh sách số nguyên tố $\le 20$: $\{2, 3, 5, 7, 11, 13, 17, 19\}$ (gồm 8 số).

3. Lý thuyết cốt lõi & bất biến toán học (core invariants)

3.1. Mối quan hệ giữa GCD và LCM

$$\gcd(A, B) \times \text{lcm}(A, B) = A \times B \implies \text{lcm}(A, B) = \frac{A}{\gcd(A, B)} \times B$$

Cảnh báo quan trọng:

Bẫy Lỗi TRÀN SỐ KHI TÍNH BỘI CHUNG NHỎ NHẤT (LCM):

• Không viết (A * B) / gcd(A, B) vì tích $A \times B$ có thể lên tới $10^{36}$ gây tràn số long long.

• Luôn viết: long long lcm = (a / gcd(a, b)) * b;

• Lưu ý chuyên sâu: Việc chia trước giúp triệt tiêu nguy cơ tràn số ở bước trung gian; tuy nhiên, nếu bản thân giá trị $\text{lcm}(A, B)$ thực tế vượt quá $9 \cdot 10^{18}$ (giới hạn của long long), ta bắt buộc phải sử dụng __int128 hoặc kiểu dữ liệu số lớn (Big Integer).

3.2. Định lý cơ bản của số học & công thức nhân tính

Mọi số nguyên $N > 1$ đều phân tích duy nhất thành tích các thừa số nguyên tố:

$$N = p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_k}$$

• Số lượng ước số của $N$ ($\sigma_0(N)$): $$\text{d}(N) = (a_1 + 1)(a_2 + 1)\dots(a_k + 1)$$

• Tổng các ước số của $N$ ($\sigma_1(N)$): $$\sigma(N) = \frac{p_1^{a_1+1} - 1}{p_1 - 1} \times \frac{p_2^{a_2+1} - 1}{p_2 - 1} \times \dots \times \frac{p_k^{a_k+1} - 1}{p_k - 1}$$

3.3. Sàng ước nguyên tố nhỏ nhất (spf - Smallest prime factor)

Thay vì chỉ lưu mảng bool, ta lưu mảng spf[x] là ước số nguyên tố nhỏ nhất của $x$.

• Phân tích thừa số nguyên tố bằng SPF cần tối đa $\mathcal{O}(\log X)$ lần chia liên tiếp, giúp trả lời cực nhanh cho hàng trăm nghìn truy vấn độc lập.

3.4. Phi hàm Euler (Euler's totient function $\phi(N)$)

Phi hàm Euler $\phi(N)$ đếm số lượng số nguyên dương trong đoạn $[1, N]$ nguyên tố cùng nhau với $N$ ($\gcd(k, N) = 1$): $$\phi(N) = N \times \left(1 - \frac{1}{p_1}\right) \times \left(1 - \frac{1}{p_2}\right) \dots \left(1 - \frac{1}{p_k}\right)$$

• Tính chất bất biến: $\sum_{d | N} \phi(d) = N$.
• Sàng Phi hàm Euler trong $\mathcal{O}(N \log \log N)$: Cho phép tính $\phi(1) \dots \phi(N)$ đồng thời trên mảng, dùng để đếm tổng số cặp số $(x, y) \le N$ thỏa mãn $\gcd(x, y) = 1$ qua công thức $2 \sum_{i=1}^N \phi(i) - 1$.

4. Các bẫy lỗi lập trình kinh điển (bug traps)

1. Tràn số khi so sánh vòng lặp căn bậc hai: * Viết for (int i = 2; i * i <= n; ++i) sẽ bị tràn số số nguyên 32-bit nếu $i \approx 46341 \implies i^2 < 0$ dẫn đến vòng lặp vô tận (TLE). * Cách sửa: Dùng 1LL * i * i <= n hoặc i <= n / i.

2. Quên xử lý phần dư cuối cùng sau khi phân tích $\mathcal{O}(\sqrt{N})$: * Sau khi chia triệt để cho các ước nguyên tố $p \le \sqrt{N}$, nếu $N > 1$ thì giá trị còn lại của $N$ chắc chắn là một số nguyên tố lớn hơn $\sqrt{N}$. Nếu bỏ qua bước này sẽ thiếu thừa số cuối cùng.

3. Số $0$ và số $1$ không phải là số nguyên tố: * Hàm kiểm tra số nguyên tố bắt buộc phải kiểm tra if (n < 2) return false;.

5. Mẫu cài đặt chuẩn thi đấu (competitive templates)

Mẫu 1: Ước chung lớn nhất & bội chung nhỏ nhất

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

// GCD bằng thuật toán Euclid lặp O(log(min(A, B)))
long long getGcd(long long a, long long b) {
    while (b != 0) {
        long long r = a % b;
        a = b;
        b = r;
    }
    return a;
}

// LCM an toàn chống tràn số
long long getLcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0;
    return (a / getGcd(a, b)) * b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long a, b;
    if (!(cin >> a >> b)) return 0;

    cout << getGcd(a, b) << " " << getLcm(a, b) << "\n";
    return 0;
}

Mẫu 2: Sàng Eratosthenes & sàng spf (tối ưu phân tích thừa số)

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

const int MAXN = 1000000;
vector<int> spf(MAXN + 1);

// Tiền xử lý Sàng SPF trong O(N log log N)
void sieveSPF() {
    for (int i = 1; i <= MAXN; ++i) spf[i] = i;
    for (int i = 2; 1LL * i * i <= MAXN; ++i) {
        if (spf[i] == i) { // i là số nguyên tố
            for (int j = i * i; j <= MAXN; j += i) {
                if (spf[j] == j) {
                    spf[j] = i;
                }
            }
        }
    }
}

// Phân tích thừa số nguyên tố O(log N) cho mỗi truy vấn
vector<pair<int, int>> factorize(int n) {

    vector<pair<int, int>> factors;

    while (n > 1) {

        int p = spf[n];
        int count = 0;
        while (n % p == 0) {
            count++;
            n /= p;
        }
        factors.push_back({p, count});
    }
    return factors;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    sieveSPF();

    int q;
    if (!(cin >> q)) return 0;

    while (q--) {
        int n;
        cin >> n;

        auto factors = factorize(n);
        for (int i = 0; i < (int)factors.size(); ++i) {
            cout << factors[i].first << "^" << factors[i].second << (i + 1 == (int)factors.size() ? "" : " * ");
        }
        cout << "\n";
    }
    return 0;
}