Elearning CodePath – CTP Online Judge

Dãy Con Dài nhất có Tổng Chia hết cho K

SUMSEQK

🟢 Easy #General #Hash

### 📌 Thông tin chung

---

### 📝 Bài toán

Cho một mảng số nguyên $A = (A_1, A_2, \dots, A_N)$ và một số nguyên dương $K$.

Yêu cầu: Tìm **độ dài của dãy con liên tiếp** (subarray) dài nhất $A[i..j]$ có tổng các phần tử **chia hết cho $K$**.

$$
\text{Tìm } \max(j - i + 1) \text{ sao cho } \sum_{l=i}^{j} A_l \equiv 0 \pmod{K}
$$

---

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

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

* **Dòng 1:** Hai số nguyên dương $N$ và $K$, cách nhau một khoảng trắng.
* **Dòng 2:** $N$ số nguyên $A_1, A_2, \dots, A_N$ (các phần tử của dãy), cách nhau một khoảng trắng.

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

> Do $N$ và $K$ đều lớn, cần một thuật toán có độ phức tạp $O(N)$ hoặc $O(N \log N)$ là tối ưu.

---

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

Ghi ra file `SUMSEQK.OUT` một số nguyên duy nhất là độ dài của dãy con dài nhất tìm được. Nếu không có dãy con nào (ngoài dãy rỗng) có tổng chia hết cho $K$, kết quả là 0.

---

### ✨ Ví dụ

| Input (`SUMSEQK.INP`) | Output (`SUMSEQK.OUT`) | Giải thích |
| :--- | :--- | :--- |
| `6 3` <br> `2 7 6 1 4 5` | `4` | Dãy con $\{7, 6, 1, 4\}$ (từ $A_2$ đến $A_5$) có tổng $7+6+1+4 = 18$. $18 \equiv 0 \pmod{3}$. |
| `7 3` <br> `-2 2 -5 12 -11 -1 7` | `5` | Dãy con $\{2, -5, 12, -11, -1\}$ (từ $A_2$ đến $A_6$) có tổng $-3$. $-3 \equiv 0 \pmod{3}$. |

---

### 💡 Gợi ý thuật toán

Sử dụng kỹ thuật **Tổng Tiền Tố (Prefix Sum)** kết hợp với tính chất modulo $K$.

1.  **Tổng Tiền Tố:** Định nghĩa $P[i]$ là tổng của $i$ phần tử đầu tiên của mảng $A$: $P[i] = \sum_{l=1}^{i} A_l$. Quy ước $P[0] = 0$.
2.  **Tính chất Modulo:** Tổng của dãy con $A[i..j]$ là $P[j] - P[i-1]$.
    $$
    \sum_{l=i}^{j} A_l \equiv 0 \pmod{K} \iff P[j] - P[i-1] \equiv 0 \pmod{K}
    $$
    $$
    \iff P[j] \equiv P[i-1] \pmod{K}
    $$
3.  **Thuật toán $O(N)$:** Duyệt qua tất cả các chỉ số $j$ (từ $1$ đến $N$). Với mỗi $j$, tính $P[j] \pmod{K}$.
    * Để tìm dãy con dài nhất kết thúc tại $j$, ta cần tìm chỉ số $i-1$ nhỏ nhất ($i-1 < j$) sao cho $P[i-1] \equiv P[j] \pmod{K}$.
    * Sử dụng một mảng $Pos[r]$ ($0 \le r < K$) để lưu trữ **chỉ số nhỏ nhất** ($i-1$) mà tổng tiền tố có giá trị modulo $K$ bằng $r$.
    * Khởi tạo $Pos[0] = 0$.
    * Trong quá trình duyệt $j$, nếu $r = P[j] \pmod{K}$ đã tồn tại trong $Pos$, thì độ dài dãy con hợp lệ là $j - Pos[r]$. Cập nhật độ dài tối đa.

Độ phức tạp tổng thể là **$O(N)$**.

✅ Đã AC: 0 / 0 submissions