Tóm tắt đề bài

Cho mảng \(A\) gồm \(n\) số nguyên không âm \(a_1, a_2, \ldots, a_n\) và số nguyên dương \(k\). Hãy tìm độ dài lớn nhất của một đoạn con liên tiếp sao cho tổng các phần tử trong đoạn chia hết cho \(k\).

Phân tích

• Ta cần tìm đoạn \([l..r]\) dài nhất sao cho: \(\sum_{i=l}^{r} a_i \equiv 0 \pmod{k}\)

• Với \(n\) lên tới \(100\,000\), không thể duyệt mọi đoạn con (\(O(n^2)\)).

• Nhận xét quan trọng dùng tổng tiền tố:

  • Gọi \(S_i = a_1 + a_2 + \cdots + a_i\), và \(S_0 = 0\).
  • Khi đó tổng đoạn \([l..r]\) là \(S_r - S_{l-1}\).
  • Điều kiện chia hết cho \(k\): \(S_r - S_{l-1} \equiv 0 \pmod{k} \iff S_r \equiv S_{l-1} \pmod{k}\)

• Vậy bài toán trở thành: tìm hai chỉ số \(i < j\) sao cho \(S_i \bmod k = S_j \bmod k\) và \(j-i\) lớn nhất.

Hướng giải quyết

Nhận xét

• Mỗi giá trị dư \(r \in [0, k-1]\) nếu xuất hiện tại các vị trí \(i_1 < i_2 < \cdots\) thì đoạn dài nhất ứng với dư đó là \(i_{\text{cuối}} - i_{\text{đầu}}\).
• Chỉ cần lưu vị trí xuất hiện đầu tiên của mỗi dư khi duyệt từ trái sang phải.
• Khi gặp lại cùng dư, ta có một đoạn con có tổng chia hết cho \(k\).

Thuật toán

1. Khởi tạo mảng first[0..k-1] lưu vị trí xuất hiện đầu tiên của từng dư, ban đầu gán -1 (chưa xuất hiện).
2. Đặt:
   • first[0] = 0 vì \(S_0 = 0\) có dư \(0\) tại vị trí \(0\) (rất quan trọng để tính các đoạn bắt đầu từ \(1\)).
   • pref = 0 (lưu \(S_i \bmod k\) khi duyệt)
   • ans = 0

3. Duyệt \(i\) từ \(1\) đến \(n\):

   • Cập nhật: \(pref = (pref + a_i) \bmod k\)

   • Nếu first[pref] == -1:

     • Gán first[pref] = i (lần đầu thấy dư này).
   • Ngược lại:
     • Độ dài đoạn hợp lệ là i - first[pref].
     • Cập nhật ans = max(ans, i - first[pref]).
   • In ans.

Trực giác vì sao đúng

• Khi cùng một dư xuất hiện lại tại vị trí \(i\), ta biết tồn tại vị trí sớm nhất first[pref] sao cho: \(S_i \equiv S_{\text{first[pref]}} \pmod{k}\)

nên đoạn \((\text{first[pref]}+1 .. i)\) có tổng chia hết cho \(k\).

• Để tối đa hóa độ dài với cùng dư, ta luôn muốn trừ cho vị trí nhỏ nhất (xuất hiện đầu tiên), nên chỉ cần lưu first.

Lỗi hay gặp

• Quên gán first[0] = 0 sẽ làm sai các đoạn bắt đầu từ phần tử đầu tiên.
• Dùng tổng tiền tố kiểu long long nếu tính tổng thật; tuy nhiên ở đây chỉ giữ modulo nên vẫn an toàn, nhưng a_i đến \(10^8\) nên cộng dồn bằng long long hoặc cộng modulo như trên.

Độ phức tạp

• Thời gian: \(O(n)\) (duyệt đúng một lần).
• Bộ nhớ: \(O(k)\), với \(k \le 1000\).

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<int> first(k, -1);   // first[r] = vị trí đầu tiên có S_i % k = r
    first[0] = 0;               // S_0 = 0 tại vị trí 0

    int ans = 0;
    int pref = 0;               // lưu S_i % k

    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        pref = (pref + (int)(x % k)) % k;

        if (first[pref] == -1) {
            first[pref] = i;    // lưu vị trí xuất hiện đầu tiên
        } else {
            ans = max(ans, i - first[pref]);
        }
    }

    cout << ans << "\n";
    return 0;
}