Bo'linuvchi qism-massivlar

$n$ ta butun sondan iborat massiv berilgan. Yig'indisi $n$ ga qoldiqsiz bo'linadigan bo'sh bo'lmagan qism-massivlar sonini toping.

Birinchi qatorda $n$ ($1 \le n \le 2 \cdot 10^5$). Ikkinchi qatorda $n$ ta butun son ($|a_i| \le 10^9$).

Bitta son — qism-massivlar soni.

$[l, r]$ yig'indisi $n$ ga bo'linadi $\iff$ $p_r \equiv p_{l-1} \pmod n$. Demak $p_0, p_1, \ldots, p_n$ qoldiqlarini sanang: qoldig'i $c$ ta marta uchragan qiymat $\frac{c(c-1)}{2}$ ta juftlik beradi. Sanoq uchun $n$ ta elementli massiv yetadi.

Manfiy sonlar bor: C++, Go va Java'da % manfiy qoldiq qaytaradi — $((p \bmod n) + n) \bmod n$ ishlating. Javob $2 \cdot 10^{10}$ gacha yetadi — 64 bitli tur kerak.

Manba: CSES, 1662-masala.