Lucas Theorem và Số học Modular Nâng cao

Wiki › Thuật toán › Toán học

Lucas Theorem và Số học Modular Nâng cao

huunguyen · Last updated 8, Tháng 4, 2026, 16:19

Lucas Theorem tính $(\binom{n}{k}) mod p$ với $p$ nguyên tố và $n, k$ lớn ( $n \leq 10^{18}$ ). Cipolla tính căn bậc hai modulo số nguyên tố.

Lucas Theorem

Định lý: Với $p$ nguyên tố, viết $n = n_{s} p^{s} + \dots + n_{1} p + n_{0}$ và $k = k_{s} p^{s} + \dots + k_{1} p + k_{0}$ trong cơ số $p$ :

(\binom{n}{k}) \equiv \prod_{i = 0}^{s} (\binom{n_{i}}{k_{i}}) (\mod p)

long long C_mod_p(long long n, long long k, long long p) {
    if (k > n) return 0;
    if (k == 0) return 1;
    return C_small(n % p, k % p, p) * C_mod_p(n / p, k / p, p) % p;
}

// C_small: tính C(n,k) với n,k < p (dùng precompute hoặc trực tiếp)
long long C_small(long long n, long long k, long long p) {
    if (k > n) return 0;
    // Tính n! / (k! * (n-k)!) mod p, n < p nên không có factor p
    long long num = 1, den = 1;
    for (long long i = 0; i < k; i++) {
        num = num * ((n - i) % p) % p;
        den = den * ((i + 1) % p) % p;
    }
    return num % p * power(den, p - 2, p) % p;
}

Độ phức tạp: $O (\log_{p} n \cdot p)$ mỗi truy vấn (hoặc $O (\log_{p} n)$ nếu precompute factorial mod $p$ ).

Lucas Theorem mở rộng (Andrew Granville)

Với $p^{e}$ không nhất thiết là số nguyên tố (mod prime power), dùng Granville's generalization. Trường hợp $p$ nguyên tố, $e > 1$ , cần Andrew Granville's formula:

// C(n, k) mod p^e — phức tạp hơn, cần factorization của n! mod p^e
// Dùng khi p nhỏ (p^e <= 10^6) và n lớn

Precompute cho nhiều truy vấn — $O (p + Q \log_{p} n)$

const int MAXP = 1e6 + 5;
long long fact[MAXP], inv_fact[MAXP];
long long P;

void precompute_lucas(long long p) {
    P = p;
    fact[0] = 1;
    for (int i = 1; i < p; i++) fact[i] = fact[i-1] * i % p;
    inv_fact[p-1] = power(fact[p-1], p-2, p);
    for (int i = p-2; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % p;
}

long long C_lucas(long long n, long long k) {
    if (k > n || k < 0) return 0;
    long long ans = 1;
    while (n > 0 || k > 0) {
        long long ni = n % P, ki = k % P;
        if (ki > ni) return 0;
        ans = ans * fact[ni] % P * inv_fact[ki] % P * inv_fact[ni-ki] % P;
        n /= P; k /= P;
    }
    return ans;
}

Cipolla — Căn bậc hai modulo số nguyên tố

Tìm $x$ sao cho $x^{2} \equiv n (\mod p)$ (p nguyên tố lẻ).

Điều kiện tồn tại: $n^{(p - 1) / 2} \equiv 1 (\mod p)$ (Legendre symbol = 1).

// Tìm x với x^2 ≡ n (mod p)
// Trả về -1 nếu không tồn tại
long long cipolla(long long n, long long p) {
    n %= p;
    if (n == 0) return 0;
    if (power(n, (p-1)/2, p) != 1) return -1;   // không tồn tại
    if (p % 4 == 3) return power(n, (p+1)/4, p);  // trường hợp đặc biệt

    // Tìm a sao cho a^2 - n là thặng dư không bậc 2
    long long a = 0;
    while (power((a*a - n % p + p) % p, (p-1)/2, p) != p-1) a++;

    // Tính (a + sqrt(a^2-n))^{(p+1)/2} trong GF(p^2)
    long long w2 = (a*a - n % p + p) % p;
    // Nhân trong GF(p^2): (x0 + x1*w) * (y0 + y1*w) với w^2 = w2
    using P2 = pair<long long, long long>;
    auto mul = [&](P2 x, P2 y) -> P2 {
        return {
            (x.first * y.first + x.second * y.second % p * w2) % p,
            (x.first * y.second + x.second * y.first) % p
        };
    };
    P2 res = {1, 0}, base = {a, 1};
    long long exp = (p + 1) / 2;
    for (; exp > 0; exp >>= 1) {
        if (exp & 1) res = mul(res, base);
        base = mul(base, base);
    }
    // res.second phải = 0
    return min(res.first, p - res.first);
}

Primitive Root (Căn nguyên thủy)

Phần tử $g$ là primitive root mod $p$ nếu $g^{1}, g^{2}, \dots, g^{p - 1}$ là hoán vị của $1, \dots, p - 1$ :

bool is_primitive_root(long long g, long long p) {
    // Kiểm tra g^{(p-1)/q} != 1 (mod p) với mọi ước nguyên tố q của p-1
    long long phi = p - 1;   // p nguyên tố
    auto factors = factorize(phi);
    for (auto [q, e] : factors)
        if (power(g, phi / q, p) == 1) return false;
    return true;
}

long long find_primitive_root(long long p) {
    for (long long g = 2; ; g++)
        if (is_primitive_root(g, p)) return g;
}

Khi nào dùng?

Bài toán	Công cụ
$(\binom{n}{k}) mod p$ , $n \leq 10^{18}$ , $p$ nhỏ	Lucas Theorem
$x^{2} \equiv n (\mod p)$	Cipolla
Logarithm rời rạc, DFT trong $ℤ / p ℤ$	Primitive root
$(\binom{n}{k}) mod p^{e}$	Granville/Andrew Lucas

Bình luận

Không có bình luận tại thời điểm này.