Editorial for Chia hết

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

Nguồn: CSES

Gọi $s(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$ ~a_l+a_{l+1}+...+a_r~ chia hết cho $n$ ~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$ ~n~ đã xuất hiện.

Vì mỗi giá trị của tổng tiền tố modulo $n$ ~n~ nằm trong khoảng từ $0$ ~0~ đến $n-1$ ~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)$ ~O(n)~

Editorial for Chia hết

Comments