Hướng giải: Chia hết

Nguồn: CSES

Gọi ~s(i)~ là tổng tiền tố (prefix sum): \(s(i)=a_1​+a_2​+...a_i​\). Tổng của một đoạn con ~a_l+a_{l+1}+...+a_r~ chia hết cho ~n~ khi và chỉ khi:

$$\displaystyle s(r) \; \text{mod} \; n = s(l-1) \; \text{mod} \; n$$

Do đó, ta có thể giải bài toán bằng cách đếm số lần mỗi giá trị của tổng tiền tố modulo ~n~ đã xuất hiện.

Vì mỗi giá trị của tổng tiền tố modulo ~n~ nằm trong khoảng từ ~0~ đến ~n-1~, ta có thể sử dụng một vector để lưu số lần xuất hiện của chúng. Lưu ý rằng cần xử lý cẩn thận phép modulo vì tổng tiền tố có thể là số âm.

Độ phức tạp: ~O(n)~