Đếm số lượng dãy con liên tiếp chia hết cho k c++

Để đếm số lượng dãy con liên tiếp chia hết cho k trong C++, chúng ta có thể thực hiện các bước sau:

1. Khởi tạo biến: Chúng ta cần một biến để đếm số lượng dãy con thỏa mãn điều kiện chia hết cho k và một biến lưu trữ tổng giá trị của dãy con hiện tại.

2. Duyệt mảng: Sử dụng vòng lặp để duyệt qua từng phần tử của mảng.

3. Tính tổng liên tiếp: Trong vòng lặp, chúng ta sẽ tính tổng của các số từ điểm bắt đầu đến điểm hiện tại. Mỗi khi tổng này chia hết cho k, chúng ta tăng biến đếm lên một.

4. Quản lý tổng: Khi tính tổng, nếu tổng hiện tại không chia hết cho k, chúng ta tiếp tục thêm phần tử tiếp theo và kiểm tra lại.

5. Xuất kết quả: Cuối cùng, in ra số lượng dãy con tìm thấy.

Dưới đây là một đoạn mã C++ minh họa cho quy trình trên:

```cpp
#include
#include

using namespace std;

int countSubarraysDivByK(vector& nums, int k) {
int count = 0;
int sum = 0;
// Sử dụng một mảng để lưu trữ số lần xuất hiện của mỗi tổng modulo k
vector remainder(k, 0);
remainder[0] = 1; // Khởi tạo với trường hợp tổng = 0

for (int num : nums) {
sum += num;
// Tính giá trị của sum mod k để nhận được tổng hiện tại
int mod = (sum % k + k) % k; // đảm bảo mod không âm
count += remainder[mod]; // Tăng số lượng dãy con nếu tìm thấy mod
remainder[mod]++; // Tăng số lần gặp mod này
}

return count;
}

int main() {
vector nums = {1, 2, 3, 4, 5};
int k = 5;
cout << "Số lượng dãy con liên tiếp chia hết cho " << k << " là: " << countSubarraysDivByK(nums, k) << endl;
return 0;
}
```

Giải thích:

- Chúng ta sử dụng một vector `remainder` để đếm số lần mà tổng (mod k) xuất hiện. Bằng cách này, chúng ta có thể theo dõi được có bao nhiêu dãy con có tổng chia hết cho k thông qua việc so sánh các tổng đang tính với các tổng đã lưu trữ trước đây.
- Việc tính `(sum % k + k) % k` là cần thiết để xử lý trường hợp giá trị âm khi tổng là âm.
- Cuối cùng, chúng ta in ra số lượng dãy con thỏa mãn yêu cầu.

Đoạn mã này sẽ giúp chúng ta tìm số lượng dãy con liên tiếp chia hết cho một số `k` rất hiệu quả với độ phức tạp thời gian là O(n).