Bài 3 HSG11 Bắc Giang 2023.

Cho số nguyên dương n và dãy số a gồm n số nguyên a₁, a₂, ..., a_n. Một dãy con liên tiếp của dãy số a có dạng a_i, a_i+1, …, a_j với 1 ≤ i ≤ j ≤ n, tổng của dãy con liên tiếp a_i, a_i+1, …, a_j là a_i + a_i+1 + … + a_j.

Em hãy đếm số lượng dãy con liên tiếp của dãy số a đã cho có tổng các phần tử của dãy con này chia hết cho số nguyên dương k.

* Dữ liệu vào: Đọc vào từ file văn bản CHIAK.INP gồm:

- Dòng 1 ghi 2 số nguyên dương n và k (n≤ 10⁶, k ≤ 10⁹). Các số trên cùng một dòng cách nhau ít nhất một khoảng trống;

- Dòng 2 ghi lần lượt các số nguyên a₁, a₂, .., a_n (|a_i| ≤ 10⁹, i=1..n). Các số trên cùng một dòng cách nhau ít nhất một khoảng trống.

* Kết quả ra: Ghi ra file văn bản CHIAK.OUT một số duy nhất là số lượng dãy con có tổng các phần tử chia hết cho k.