Hiểu bài toán

Cho một số nguyên dương n (1 ≤ n ≤ 10^18). Xác định xem số L = (n - 1)! + 1 có chia hết cho n hay không. Nói cách khác, kiểm tra điều kiện (n - 1)! ≡ -1 (mod n).

Các cách tiếp cận

Cách Brute Force (Tính trực tiếp)

void solve() {
    long long n;
    cin >> n;
    if (n == 1) {
        cout << "YES";
        return;
    }
    long long fact = 1;
    for (int i = 2; i < n; i++) {
        fact *= i;
        fact %= n; // Giai thua nho hon n, nhung n co the lon
    }
    if ((fact + 1) % n == 0) cout << "YES";
    else cout << "NO";
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Approach này tính trực tiếp giá trị (n-1)! mod n bằng vòng lặp từ 2 đến n-1. Tuy nhiên, với n lên tới 10^18, độ phức tạp O(n) là không thể chấp nhận được. Ví dụ, nếu n = 10^18, vòng lặp sẽ không bao giờ kết thúc trong thời gian cho phép. Approach này chỉ khả thi cho các bài toán với n nhỏ (ví dụ n ≤ 10^6).

Cách Sử dụng Định lý Wilson

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(long long n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (long long i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

int main() {
    long long n;
    cin >> n;
    if (n == 1) {
        cout << "YES";
        return 0;
    }
    if (isPrime(n)) {
        cout << "YES";
    } else {
        cout << "NO";
    }
    return 0;
}

• Time Complexity: O(√n)
• Space Complexity: O(1)

Định lý Wilson phát biểu rằng (p-1)! ≡ -1 (mod p) nếu và chỉ nếu p là số nguyên tố. Do đó, bài toán quy về việc kiểm tra xem n có phải là số nguyên tố hay không (trừ trường hợp n=1).

Cách tiếp cận này:

1. Nếu n = 1: (0)! + 1 = 2, 2 chia hết cho 1 (theo quy ước số nguyên dương chia hết cho 1). Output YES.
2. Nếu n > 1: L = (n-1)! + 1 chia hết cho n khi và chỉ khi n là số nguyên tố.

Code sử dụng sàng nguyên tố cơ bản (kiểm tra ước đến √n) để kiểm tra tính nguyên tố của n. Độ phức tạp O(√n), với n = 10^18 thì √n ≈ 10^9, vẫn quá lớn để chạy trong 1 giây.

Lưu ý: Solution này đúng về mặt lý thuyết nhưng cần tối ưu hóa thêm (kiểm tra các số nhỏ trước, chỉ lặp số lẻ...) để chạy nhanh hơn. Tuy nhiên, với 10^18, O(√n) vẫn là bottleneck.

Cách Miller-Rabin Primality Test (Optimal)

#include <bits/stdc++.h>
using namespace std;
using u64 = uint64_t;
using u128 = __uint128_t;

// Nhân modulo an toàn với 128-bit
u64 mul_mod(u64 a, u64 b, u64 m) {
    return (u128)a * b % m;
}

// Lũy thừa modulo an toàn
u64 pow_mod(u64 a, u64 e, u64 m) {
    u64 res = 1;
    a %= m;
    while (e) {
        if (e & 1) res = mul_mod(res, a, m);
        a = mul_mod(a, a, m);
        e >>= 1;
    }
    return res;
}

// Kiểm tra Miller-Rabin Deterministic cho 64-bit
bool isPrime(u64 n) {
    if (n < 2) return false;
    // Kiểm tra các số chia hết nhỏ
    for (u64 p : {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL}) {
        if (n % p == 0) return n == p;
    }

    u64 d = n - 1;
    int s = 0;
    while ((d & 1) == 0) {
        d >>= 1;
        s++;
    }

    // Các base deterministic cho n < 2^64
    for (u64 a : {2ULL, 325ULL, 9375ULL, 28178ULL, 450775ULL, 9780504ULL, 1795265022ULL}) {
        if (a % n == 0) continue;
        u64 x = pow_mod(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool composite = true;
        for (int r = 1; r < s; r++) {
            x = mul_mod(x, x, n);
            if (x == n - 1) {
                composite = false;
                break;
            }
        }
        if (composite) return false;
    }
    return true;
}

int main() {
    u64 n;
    cin >> n;
    // Truong hop dac biet n = 1
    if (n == 1) {
        cout << "YES";
        return 0;
    }
    // Dung dinh ly Wilson: (n-1)! + 1 chia het cho n <=> n la so nguyen to
    if (isPrime(n)) cout << "YES";
    else cout << "NO";
    return 0;
}

• Time Complexity: O(k * log^3 n) ~ O(log^3 n)
• Space Complexity: O(1)

Đây là approach tối ưu nhất. Nó kết hợp Định lý Wilson và Thử nghiệm Miller-Rabin.

1. Logic: (n-1)! + 1 chia hết cho n nếu và chỉ nếu n là số nguyên tố (với n > 1). Nếu n = 1, đáp án là YES.
2. Thực hiện: Thay vì sàng đến √n (O(√n)), ta sử dụng thuật toán Miller-Rabin để kiểm tra tính nguyên tố.
   • Miller-Rabin là thuật toán xác suất, nhưng với các base cố định đặc biệt (ví dụ: 2, 325, 9375,...), nó trở thành thuật toán xác định cho n < 2^64 (tức là n ≤ 10^18).
   • Thuật toán này có độ phức tạp O(log^3 n) hoặc O(log^2 n) tùy cách tính, rất nhanh so với O(√n).

Code sử dụng __uint128_t (tính năng mở rộng của C++) để thực hiện nhân modulo chính xác mà không bị tràn số, cần thiết vì a * b có thể vượt quá giới hạn 64-bit của unsigned long long khi a, b gần bằng n (10^18).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Sử dụng Định lý Wilson: (n-1)! ≡ -1 (mod n) khi và chỉ khi n là số nguyên tố. Điều này biến bài toán kiểm tra chia hết thành bài toán kiểm tra tính nguyên tố.
• Với giới hạn n ≤ 10^18, sàng nguyên tố thông thường (O(√n)) là không đủ. Phải sử dụng các thuật toán kiểm tra nguyên tố nhanh như Miller-Rabin.
• Cần xử lý trường hợp đặc biệt n = 1 vì 1 không phải là số nguyên tố nhưng (0)! + 1 = 2 chia hết cho 1.

Lỗi thường gặp

• Quên xử lý trường hợp n = 1: n = 1 là số nguyên dương, (1-1)! + 1 = 2. 2 chia hết cho 1 nên kết quả là YES.
• Sử dụng kiểu dữ liệu 64-bit (long long) để tính toán khi nhân hai số lớn (gần 10^18) trong quá trình tính lũy thừa modulo. Ví dụ: a * b % mod với a, b ~ 10^18 sẽ tràn số. Cần dùng 128-bit (__int128) hoặc thuật toán nhân modulo đặc biệt.
• Sai base trong Miller-Rabin: Nếu chỉ dùng base {2}, Miller-Rabin sẽ sai lệch cho các số Carmichael (ví dụ 561). Với n ≤ 10^18, cần dùng một tập hợp base mạnh (deterministic) như {2, 325, 9375, 28178, 450775, 9780504, 1795265022}.