Bài 4. Đề Cụm lớp 12 - TÂN KỲ - NA 2023

Cho một dãy số nguyên dương, yêu cầu hãy đếm số lượng dãy con liên tiếp có tổng chia hết cho d. Hai dãy con được gọi là khác nhau nếu ít nhất một trong hai điểm đầu hoặc điểm cuối hai dãy con đó trong dãy đã cho là khác nhau.

Ví dụ với d=4, dãy (2,1,2,1,4,1) có 4 dãy con thỏa mãn là (1,2,1), (1,2,1,4),(4),(2,1,4,1). Với d=2 và dãy (1,1,1,1) thì có 4 dãy con thỏa mãn.  

Dữ liệu: Vào từ file văn bản Bai4.inp gồm 2 dòng:

• Dòng đầu là 2 số nguyên dương d và N (d  ≤ 10⁶, N ≤  10⁵)
• Dòng thứ 2 chứa N số nguyên dương biểu diễn dãy số, các số trong dãy không quá 10⁹.

Kết quả: Ghi ra file văn bản Bai4.out gồm 1 số duy nhất là kết quả tìm được.