Hướng dẫn giải của Đếm bộ ba số

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, playerpro, Datek, anhnguyenhoang117

Hiểu bài toán

Cho mảng gồm n số nguyên không âm a1, a2, ..., an và số nguyên dương M. Hãy đếm số bộ ba chỉ số (i, j, k) (1 ≤ i, j, k ≤ n) sao cho tích ai × aj × ak chia hết cho M. Lưu ý các bộ ba có thứ tự khác nhau (hoán vị) được tính là khác nhau.

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

Cách Quy hoạch động theo các ước của M
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;

    // Liệt kê tất cả các ước của M
    vector<int> divisors;
    for (int i = 1; i * i <= m; ++i) {
        if (m % i == 0) {
            divisors.push_back(i);
            if (i * i != m) divisors.push_back(m / i);
        }
    }
    sort(divisors.begin(), divisors.end());

    // Ánh xạ ước sang chỉ số để truy cập O(1)
    int d = divisors.size();
    vector<int> pos(m + 1, -1);
    for (int i = 0; i < d; ++i) {
        pos[divisors[i]] = i;
    }

    // dp[x]: số cách chọn 2 số sao cho gcd tích của chúng với M là divisors[x]
    // Ban đầu dp dùng để đếm số cách chọn 1 số
    vector<long long> dp(d, 0);

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        int g = gcd(x, m);
        // Nếu g không phải ước của m (do x=0?) thì g=0? gcd(0, m)=m. 
        // Nếu x=0, gcd(0, m)=m, là ước của m.
        if (pos[g] != -1) {
            dp[pos[g]]++;
        }
    }

    // Tính số cách chọn 2 số (tổng quát là k số)
    // new_dp[y] = sum(dp[x] * count(new_gcd))
    // Tuy nhiên, cách này cần xử lý cẩn thận.
    // Ta có thể dùng DP gom nhóm theo gcd của tích.
    // dp[len][idx]: số cách chọn len số sao cho gcd tích vs M là divisors[idx]
    // Kích thước mảng dp: 2 * d (hoặc 3 * d)

    vector<long long> ways(2 * d, 0); // ways[0...d-1]: len=1, ways[d...2d-1]: len=2
    // Copy từ dp (len=1) vào ways
    for (int i = 0; i < d; ++i) ways[i] = dp[i];

    // Tính len=2
    for (int x = 0; x < d; ++x) {
        if (dp[x] == 0) continue;
        for (int y = 0; y < d; ++y) {
            if (dp[y] == 0) continue;
            long long mul = 1LL * divisors[x] * divisors[y];
            // gcd(mul, m)
            int g = gcd((int)(mul % m), m); // Cẩn thận tràn số, nhưng divisors <= m <= 3000 nên 1LL * m * m <= 9e6, an toàn.
            // Hoặc dùng __gcd((long long)divisors[x] * divisors[y], (long long)m)
            int idx = pos[g];
            ways[d + idx] += dp[x] * dp[y];
        }
    }

    // Tính len=3 và lấy kết quả
    long long ans = 0;
    vector<long long> ways3(d, 0);
    // ways3[idx] la so cach chon 3 so

    // Tu ways (len=2) và dp (len=1)
    // Hoặc直接 dùng 3 vòng lặp

    for (int x = 0; x < d; ++x) {
        if (dp[x] == 0) continue;
        for (int y = 0; y < d; ++y) {
            if (dp[y] == 0) continue;
            // Tính tích 2 số trước
            long long mul2 = 1LL * divisors[x] * divisors[y];
            int g2 = (int)__gcd(mul2, (long long)m);
            int idx2 = pos[g2];

            // Kết hợp với số thứ 3
            for (int z = 0; z < d; ++z) {
                if (dp[z] == 0) continue;
                long long mul3 = mul2 * divisors[z];
                // Nếu tích chia hết cho m
                // Kiểm tra nhanh: gcd(g2 * divisors[z], m)
                if (__gcd(mul3, (long long)m) == m) {
                    ans += dp[x] * dp[y] * dp[z];
                }
            }
        }
    }

    cout << ans << endl;
    return 0;
}
  • Time Complexity: O(d^2 * D) hoặc O(d^3). D là số lượng ước của M. Với M <= 3000, số lượng ước nhỏ (max ~32). Nên hiệu quả.
  • Space Complexity: O(D) ~ O(1)

Phương pháp này dựa trên quan sát rằng điều kiện chia hết cho M phụ thuộc vào các thừa số nguyên tố của M. Thay vì quan tâm giá trị cụ thể của ai, ta chỉ quan tâm đến gcd(ai, M). Gọi G là tập hợp các ước của M. Với mỗi ai, ta tính gi = gcd(ai, M). Gọi cnt[g] là số lượng các ai có gcd bằng g.

Số bộ ba (i, j, k) thỏa mãn là: $$ \sum_{x, y, z \in G} cnt[x] \times cnt[y] \times cnt[z] \times \mathbb{I}(x \times y \times z \text{ chia hết cho } M) $$

Trong đó điều kiện $x \times y \times z \text{ chia hết cho } M$ có thể kiểm tra bằng cách tính $\gcd(x \times y \times z, M) = M$.

Do M nhỏ (<= 3000), số lượng ước D khá nhỏ (nhỏ hơn 60), nên ta có thể duyệt qua tất cả các bộ 3 ước (x, y, z) để tính kết quả. Độ phức tạp là $O(D^3)$, rất nhanh.

Cách Quy hoạch động tuyến tính theo M
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    int n, m;
    if (!(cin >> n >> m)) return 0;

    // cnt[x]: số lượng a_i sao cho gcd(a_i, m) == x
    vector<ll> cnt(m + 1, 0);

    // dp[k][x]: số cách chọn k số sao cho (tích các số được chọn) % m == x
    // Tuy nhiên, tích có thể rất lớn. Ta chỉ cần xem xét modulo m.
    // dp[k][x] là số cách chọn k số sao cho tích modulo m là x.
    // Kích thước mảng: (n+1) * m. n len 10^6 -> kha lon.
    // Can thay doi: chi can k=1, 2, 3.

    vector<ll> cnt_mod(m, 0);
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (x == 0) {
            // 0 * anything = 0. Neu chon 0, toc do chia het cho M luon.
            // Xử lý riêng cho 0.
            // De don gian, ta co the co 1 bien dem so luong 0.
            // Hoặc coi 0 là gcd(0, m) = m.
            // Neu a_i = 0, thi a_i % m = 0.
            // De xu ly theo phuong phap duoi day, ta co the coi 0 la 0.
        }
        cnt_mod[x % m]++;
    }

    // dp[j]: so cach chon 1 so sao cho tich % m == j
    vector<ll> dp1 = cnt_mod;

    // dp2[j]: so cach chon 2 so sao cho tich % m == j
    vector<ll> dp2(m, 0);
    for (int i = 0; i < m; ++i) {
        if (dp1[i] == 0) continue;
        for (int j = 0; j < m; ++j) {
            if (dp1[j] == 0) continue;
            dp2[(i * j) % m] += dp1[i] * dp1[j];
        }
    }

    // dp3[j]: so cach chon 3 so sao cho tich % m == j
    // Chi can tinh dp3[0] (vi chia het cho M khi va chi khi tich % m == 0)
    // Tuy nhien, cach nay phuc tap O(m^2).
    // Neu m=3000, m^2 = 9e6, acceptable.

    ll ans = 0;
    // Tinh so cach chon 3 so co tich % m == 0
    // Su dung dp2 va dp1
    for (int i = 0; i < m; ++i) {
        if (dp2[i] == 0) continue;
        for (int j = 0; j < m; ++j) {
            if (dp1[j] == 0) continue;
            if ((i * j) % m == 0) {
                ans += dp2[i] * dp1[j];
            }
        }
    }

    cout << ans << endl;
    return 0;
}
  • Time Complexity: O(m^2) hoặc O(m^2 log n) tùy cách tính. Với m <= 3000, m^2 ~ 9 * 10^6, rất nhanh.
  • Space Complexity: O(m)

Phương pháp này sử dụng quy hoạch động dựa trên giá trị của các số theo modulo M. Gọi dp[k][r] là số cách chọn k số sao cho tích của chúng có dư chia cho M bằng r.

Bài toán quy về tìm dp[3][0].

Công thức truy hồi:

  • dp[1][r] = số lượng ai có ai % M == r.
  • dp[k][r'] = sum(dp[k-1][r] * count(x) * [r * x % M == r'])

Vì M nhỏ (<= 3000), ta có thể tính trực tiếp:

  1. Tính mảng cnt_mod đếm số lượng phần tử có giá trị mod M bằng r.
  2. Tính dp2[r] (chọn 2 số): Duyệt qua tất cả các cặp (i, j) và cập nhật dp2[(i*j)%M] += cntmod[i] * cntmod[j].
  3. Tính kết quả: Duyệt qua tất cả các cặp (i, j) sao cho (i*j)%M == 0, cộng dồn dp2[i] * cnt_mod[j] vào kết quả.

Độ phức tạp là $O(M^2)$, với $M \le 3000$ thì hoàn toàn khả thi.

Cách Gom nhóm theo ước của M (Tối ưu)
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    if (!(cin >> n >> m)) return 0;

    // Liệt kê các ước của M
    vector<int> divisors;
    for (int i = 1; i * i <= m; ++i) {
        if (m % i == 0) {
            divisors.push_back(i);
            if (i * i != m) divisors.push_back(m / i);
        }
    }
    sort(divisors.begin(), divisors.end());
    int d = divisors.size();

    // Map ước sang index
    vector<int> pos(m + 1, -1);
    for (int i = 0; i < d; ++i) pos[divisors[i]] = i;

    // cnt[idx]: số lượng a_i sao cho gcd(a_i, m) == divisors[idx]
    vector<long long> cnt(d, 0);

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        int g = gcd(x, m);
        if (pos[g] != -1) cnt[pos[g]]++;
    }

    long long ans = 0;

    // Duyệt qua tất cả các bộ 3 ước (i, j, k)
    // Tối ưu: Sắp xếp divisors để break early (ít tác dụng do D nhỏ)
    // Tính tích các ước

    for (int i = 0; i < d; ++i) {
        if (cnt[i] == 0) continue;
        for (int j = 0; j < d; ++j) {
            if (cnt[j] == 0) continue;
            for (int k = 0; k < d; ++k) {
                if (cnt[k] == 0) continue;

                // Kiểm tra xem divisors[i] * divisors[j] * divisors[k] có chia hết cho m không
                // Sử dụng __gcd để tránh tràn số
                long long p1 = 1LL * divisors[i] * divisors[j];
                // p1 có thể lớn, nhưng m <= 3000, ước <= 3000. p1 max ~ 9e6. An toàn.
                if ((p1 % m == 0) && (1LL * divisors[k] == 1 || (p1 * divisors[k]) % m == 0)) {
                     // Cach 1: Neu p1 chia het m thi ket qua luon chia het
                     // Cach 2: Tinh toan day du
                }

                // Cach chinh xac va an toan:
                // Neu (divisors[i] * divisors[j] * divisors[k]) % m == 0
                // Tranh truong hop trung so 0 neu a_i = 0 (gcd(0, m) = m)

                long long mul = 1LL * divisors[i] * divisors[j] * divisors[k];
                // Voi m <= 3000, mul <= 3000^3 = 27e9, chua vuot qua kieu long long (9e18)
                // Tuy nhien de an toan, dung gcd
                // if (mul % m == 0) ans += cnt[i] * cnt[j] * cnt[k];

                if (mul % m == 0) {
                    ans += cnt[i] * cnt[j] * cnt[k];
                }
            }
        }
    }

    cout << ans << endl;
    return 0;
}
  • Time Complexity: O(D^3), D là số lượng ước của M (D <= 60).
  • Space Complexity: O(D)

Đây là phiên bản chi tiết của Approach 1. Bước 1: Liệt kê tất cả các ước của M và lưu vào mảng divisors. Số lượng ước D rất nhỏ. Bước 2: Với mỗi phần tử ai, tính g = gcd(ai, M). Tăng biến đếm cnt[g] lên 1. Bước 3: Duyệt 3 vòng lặp qua các ước x, y, z trong divisors. Nếu x * y * z chia hết cho M, cộng cnt[x] * cnt[y] * cnt[k] vào kết quả.

Lưu ý:

  • a_i có thể bằng 0. Khi đó gcd(0, M) = M. M luôn là ước của M, nên pos[M] sẽ tồn tại và cnt[M] sẽ đếm số lượng số 0.
  • Kiểm tra x * y * z % M == 0.

Với M <= 3000, số ước tối đa là 32 (tại 2520). D^3 ~ 32^3 ~ 32,000, quá nhanh.

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

Cách tiếp cận Time Space Tên
1 O(d^2 * D) hoặc O(d^3). D là số lượng ước của M. Với M <= 3000, số lượng ước nhỏ (max ~32). Nên hiệu quả. O(D) ~ O(1) Quy hoạch động theo các ước của M
2 O(m^2) hoặc O(m^2 log n) tùy cách tính. Với m <= 3000, m^2 ~ 9 * 10^6, rất nhanh. O(m) Quy hoạch động tuyến tính theo M
3 O(D^3), D là số lượng ước của M (D <= 60). O(D) Gom nhóm theo ước của M (Tối ưu)

Bài học kinh nghiệm

  • Bài toán chỉ phụ thuộc vào gcd(ai, M) thay vì giá trị thực của ai.
  • M có giới hạn nhỏ (<= 3000) cho phép sử dụng các thuật toán có độ phức tạp phụ thuộc vào M (như O(M^2), O(D^3)).
  • Xử lý số 0: gcd(0, M) = M, cần đưa M vào danh sách các ước được xét.

Lỗi thường gặp

  • Quên xử lý trường hợp a_i = 0, dẫn đến việc bỏ sót các bộ ba chứa số 0.
  • Tràn số khi tính tích các ước nếu không sử dụng long long hoặc kiểm tra chia hết sớm.
  • Bỏ qua các bộ ba có thứ tự khác nhau (hoán vị). Các solution đều tính toán full bộ 3 chỉ số (i, j, k) không phân biệt thứ tự, nên yêu cầu về hoán vị được đáp ứng tự nhiên.

Bình luận

Please read the guidelines before commenting.

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