Tóm tắt đề bài

Cho ba số tự nhiên \(n, k, m\). Hãy tính giá trị của tổ hợp chập \(k\) của \(n\) chia lấy dư cho \(m\).
Công thức tổ hợp:

Yêu cầu: Tính \(C_n^k \pmod m\).

Phân tích

• Ràng buộc: \(n \le 10^5\), \(m \le 10^9\).
• Vấn đề: Thông thường, để tính \(C_n^k \pmod m\), ta sử dụng nghịch đảo modulo. Tuy nhiên, phương pháp này chỉ áp dụng được khi \(m\) là số nguyên tố và \(k!(n-k)!\) nguyên tố cùng nhau với \(m\). Ở bài này, \(m\) có thể là bất kỳ số tự nhiên nào lên đến \(10^9\), do đó ta không thể dùng nghịch đảo modulo trực tiếp.
• Ý tưởng: Mọi số tự nhiên đều có thể phân tích thành tích các thừa số nguyên tố. Ta sẽ tìm số mũ của từng số nguyên tố \(p\) trong phân tích thừa số nguyên tố của \(C_n^k\).
  • Gọi \(v_p(x)\) là số mũ của số nguyên tố \(p\) trong phân tích của \(x\).
  • Ta có: \(v_p(C_n^k) = v_p(n!) - v_p(k!) - v_p((n-k)!)\).
  • Để tính \(v_p(n!)\), ta sử dụng Công thức Legendre.

Hướng giải quyết

1. Công thức Legendre

Số mũ của số nguyên tố \(p\) trong \(n!\) được tính bằng công thức:

Vòng lặp sẽ dừng lại khi \(p^i > n\).

2. Thuật toán

1. Sàng số nguyên tố: Sử dụng sàng Eratosthenes để tìm tất cả các số nguyên tố từ \(2\) đến \(10^5\) (vì \(n \le 10^5\), các thừa số nguyên tố của \(C_n^k\) không thể vượt quá \(n\)).
2. Duyệt từng số nguyên tố: Với mỗi số nguyên tố \(p\) tìm được:
   • Tính số mũ \(e = v_p(n!) - v_p(k!) - v_p((n-k)!)\).
   • Nếu \(e > 0\), ta tính \(p^e \pmod m\) bằng phương pháp lũy thừa nhị phân.
   • Nhân kết quả này vào đáp án cuối cùng và lấy dư cho \(m\).
3. Lưu ý: Cần sử dụng kiểu dữ liệu long long khi thực hiện các phép nhân để tránh tràn số trước khi lấy dư.

Độ phức tạp

• Sàng số nguyên tố: \(O(N \log \log N)\) với \(N = 10^5\).
• Xử lý mỗi truy vấn: \(O(\pi(N) \cdot \log N)\), trong đó \(\pi(N)\) là số lượng số nguyên tố nhỏ hơn hoặc bằng \(N\) (\(\pi(10^5) \approx 9592\)).
• Tổng độ phức tạp: \(O(N \log \log N + T \cdot \pi(N) \log N)\). Với các giới hạn đã cho, thuật toán này chạy đủ nhanh trong thời gian cho phép.

Code tham khảo

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e5 + 1;

bool is_prime[MAXN];
vector<int> primes;

// Hàm tính lũy thừa nhanh (x^k) % mod
int pow_mod(int x, int k, int mod) {
    if (k == 0) return 1;
    long long res = 1;
    long long base = x % mod;
    while (k > 0) {
        if (k % 2 == 1) res = (res * base) % mod;
        base = (base * base) % mod;
        k /= 2;
    }
    return (int)res;
}

// Công thức Legendre: Tính số mũ của p trong n!
int legendre(int n, int p) {
    int cnt = 0;
    while (n > 0) {
        cnt += n / p;
        n /= p;
    }
    return cnt;
}

void solve() {
    int n, k, m;
    if (!(cin >> n >> k >> m)) return;

    long long ans = 1;
    // Duyệt qua các số nguyên tố p <= n
    for (int p : primes) {
        if (p > n) break;

        // Số mũ của p trong C(n, k) = v_p(n!) - v_p(k!) - v_p((n-k)!)
        int exponent = legendre(n, p) - legendre(k, p) - legendre(n - k, p);

        if (exponent > 0) {
            ans = (ans * pow_mod(p, exponent, m)) % m;
        }
    }
    cout << ans << '\n';
}

int main() {
    // Tối ưu hóa nhập xuất
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    // Sàng Eratosthenes tìm các số nguyên tố đến 10^5
    fill(is_prime + 2, is_prime + MAXN, true);
    for (int i = 2; i * i < MAXN; ++i) {
        if (is_prime[i]) {
            for (int j = i * i; j < MAXN; j += i)
                is_prime[j] = false;
        }
    }
    for (int i = 2; i < MAXN; ++i) {
        if (is_prime[i]) primes.push_back(i);
    }

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}