Tổng mảng con chia hết cho K trong C++

Cho mảng A và số k. Đếm số mảng con liên tiếp không rỗng có tổng chia hết cho k.

Ví dụ: A = [4,5,0,-2,-3,1], k = 5 → 7 mảng con.

Thuật toán giải quyết (Prefix Sum + Hash Map)

Tổng mảng con A[i..j] chia hết cho k ⟺ (prefix[j] - prefix[i-1]) % k == 0 ⟺ prefix[j] % k == prefix[i-1] % k.

1. Map m đếm tần suất các dư, khởi tạo m[0] = 1.
2. temp = 0, ans = 0.
3. Duyệt mảng:
   • temp += A[i].
   • x = (temp % k + k) % k (dư không âm).
   • ans += m[x] (số prefix trước có cùng dư).
   • m[x]++.
4. Trả về ans.

Ví dụ minh họa (C++)

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

class Solution {
public:
    int subarraysDivByK(vector<int>& a, int k) {
        unordered_map<int, int> m;
        m[0] = 1;
        int temp = 0, ans = 0, n = a.size();
        for (int i = 0; i < n; i++) {
            temp += a[i];
            int x = (temp % k + k) % k;
            ans += m[x];
            m[x]++;
        }
        return ans;
    }
};

int main() {
    vector<int> v = {4, 5, 0, -2, -3, 1};
    Solution ob;
    cout << ob.subarraysDivByK(v, 5);
}

Đầu vào

[4,5,0,-2,-3,1] 5

Đầu ra

7