Hiểu bài toán

Cho hai số nguyên dương n và p (p là số nguyên tố). Bài toán yêu cầu đếm số lượng cặp số (j, i) thỏa mãn 0 ≤ j ≤ i < n sao cho Ci^j (hợp số chọn j từ i) chia hết cho p. Ví dụ với n=5, p=3, ta cần kiểm tra các cặp (j,i) trong khoảng đó và đếm những cặp mà Ci^j chia hết cho 3.

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

Cách Brute Force

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

ll n; int p;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll nCr(ll n, ll r) {
    if (r > n) return 0;
    if (r == 0 || r == n) return 1;
    ll res = 1;
    for (ll i = 1; i <= r; i++) {
        res = res * (n - i + 1) / i;
    }
    return res;
}

int main() {
    cin >> n >> p;
    ll ans = 0;
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j <= i; j++) {
            ll val = nCr(i, j);
            if (val % p == 0) ans++;
        }
    }
    cout << ans;
}

• Time Complexity: O(n^2 * log(n))
• Space Complexity: O(1)

Phương pháp này tính trực tiếp Ci^j cho từng cặp (j,i) bằng công thức tích lũy và kiểm tra xem nó có chia hết cho p không. Tuy nhiên, cách này rất chậm vì có O(n^2) cặp và mỗi lần tính Ci^j mất O(n). Với n < 3×10^6, cách này hoàn toàn không khả thi.

Cách Ký số theo cơ số p (Lucas Theorem)

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

int p;

ll count_non_divisible(int n) {
    ll res = 1;
    while (n > 0) {
        res *= (n % p) + 1;
        n /= p;
    }
    return res;
}

int main() {
    int n;
    cin >> n >> p;

    ll total = 1LL * n * (n + 1) / 2;
    ll good = 0;
    for (int i = 0; i < n; ++i) {
        good += count_non_divisible(i);
    }

    cout << total - good << '\n';
    return 0;
}

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

Dựa vào định lý Lucas: Ci^j không chia hết cho p khi và chỉ khi trong phân tích cơ số p của i và j,每一位数字满足 jd ≤ id. Số lượng cặp (j,i) không chia hết p là tổng số cách chọn j sao cho jd ≤ id với mọi i < n. Với mỗi i, số cách chọn j là (i0+1)(i_1+1)... где i_k là chữ số cơ số p của i. Tính tổng số cặp không chia hết rồi trừ từ tổng số cặp tổng.

Cách Tối ưu với mảng đếm

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

int main() {
    ll n; int p;
    cin >> n >> p;
    ll ans = 0;
    for (ll i = 0; i < n; i++) {
        ll x = i, f = 1;
        while (x) {
            f *= (x % p + 1);
            x /= p;
        }
        ans += (i + 1 - f);
    }
    cout << ans;
}

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

Đây là phiên bản trực tiếp của phương pháp Lucas. Với mỗi i từ 0 đến n-1, ta tính số j thỏa mãn C_i^j không chia hết p bằng cách nhân các (chữ số cơ số p của i + 1). Số j chia hết p = (i+1) - số j không chia hết. Với i=0, f=1 nên số cặp chia hết là 0. Vòng lặp từ i=0 đến n-1 tính tổng.

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

Bài học kinh nghiệm

• Sử dụng định lý Lucas để kiểm tra chia hết Ci^j cho p: Ci^j không chia hết p ⇔ với mọi chữ số cơ số p, jd ≤ id
• Tổng số cặp (j,i) là n(n+1)/2, đếm số cặp không chia hết rồi trừ đi để ra số cặp chia hết
• Với mỗi i, số cách chọn j không chia hết p bằng tích các (chữ số cơ số p của i + 1)

Lỗi thường gặp

• Quên xử lý trường hợp i=0 (khi đó f=1, không có cặp chia hết)
• Sử dụng số nguyên 32-bit không đủ lưu trữ kết quả (n có thể lên tới 3×10^6, tổng số cặp ~ 4.5×10^12)
• Tính trực tiếp C_i^j mà không dùng Lucas sẽ quá chậm và dễ tràn số