Elearning CodePath – CTP Online Judge

CHIAKEO

🟢 Hard #General

### 📌 Thông tin chung

---

### 📝 Bài toán

Cho một dãy $N$ gói kẹo $A = (A_1, A_2, \dots, A_N)$, với $A_i$ là số kẹo trong gói thứ $i$. Cho số nguyên dương $M$ (số lượng học sinh).

Yêu cầu: Đếm số lượng **cặp chỉ số** $(l, r)$ thỏa mãn:
1.  $1 \le l \le r \le N$.
2.  Tổng số kẹo trong đoạn $[l, r]$ là bội số của $M$. Tức là:
$$
\sum_{i=l}^{r} A_i \equiv 0 \pmod{M}
$$

---

### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `CHIAKEO.INP` gồm:

* **Dòng 1:** Hai số nguyên $N$ và $M$ – số gói kẹo và số học sinh.
* **Dòng 2:** $N$ số nguyên $A_1, A_2, \dots, A_N$ – số kẹo trong mỗi gói.

**Giới hạn (Ràng buộc):**
* $1 \le N \le 10^6$
* $2 \le M \le 10^9$
* $1 \le A_i \le 10^9$

**Subtasks:**
* **Subtask 1 (40%):** $N \le 100$.
* **Subtask 2 (30%):** $M \le 10^6$.
* **Subtask 3 (30%):** Không có ràng buộc bổ sung.

---

### 📤 Định dạng Đầu ra

Ghi ra file `CHIAKEO.OUT` một số nguyên duy nhất là số lượng cặp $(l, r)$ thỏa mãn điều kiện.

---

### ✨ Ví dụ

| Input (`CHIAKEO.INP`) | Output (`CHIAKEO.OUT`) | Giải thích |
| :--- | :--- | :--- |
| `3 2` `4 1 5` | `3` | Dãy $A=[4, 1, 5]$, $M=2$. Tổng chia hết cho 2: 1. $(l, r) = (1, 1): 4 \equiv 0 \pmod{2}$. 2. $(l, r) = (1, 3): 4+1+5 = 10 \equiv 0 \pmod{2}$. 3. $(l, r) = (2, 3): 1+5 = 6 \equiv 0 \pmod{2}$. |

✅ Đã AC: 2 / 6 submissions