Đếm cặp trong mảng có tổng chia hết cho K trong C++

Giới thiệu

Cho mảng số nguyên và số k. Đếm số cặp (i, j) với i < j sao cho (arr[i] + arr[j]) % k == 0.

Ví dụ

• arr = [4,1,2,0,2], k = 2 → 6 cặp
• arr = [2,4,8,6,10], k = 4 → 4 cặp

Ý tưởng giải thuật tối ưu O(n + k)

1. Đếm tần suất phần dư: freq[r] = số phần tử có arr[i] % k == r.
2. Cặp chia hết cho k khi tổng phần dư = 0 hoặc k:
   • Phần dư 0: cặp trong nhóm → freq[0] * (freq[0]-1) / 2
   • Phần dư r và k-r (1 ≤ r < k/2): freq[r] * freq[k-r]
   • Nếu k chẵn, phần dư k/2: freq[k/2] * (freq[k/2]-1) / 2

Ví dụ triển khai (C++)

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

long long countDivisibleSumPairs(vector<int> arr, int k) {
    vector<long long> freq(k, 0);
    for (int x : arr)
        freq[x % k]++;
    
    long long count = 0;
    // Phần dư 0
    count += freq[0] * (freq[0] - 1) / 2;
    
    // Phần dư r và k-r
    for (int r = 1; r <= k/2 && r != k-r; r++)
        count += freq[r] * freq[k-r];
    
    // Phần dư k/2 khi k chẵn
    if (k % 2 == 0)
        count += freq[k/2] * (freq[k/2] - 1) / 2;
    
    return count;
}

int main() {
    vector<int> arr = {4, 1, 2, 0, 2};
    int k = 2;
    cout << "So cap tong chia het cho " << k << ": " << countDivisibleSumPairs(arr, k); // 6
    return 0;
}

Đầu vào

[4,1,2,0,2], k=2

Đầu ra

6