Candy Distribution

题目描述

有 $N$ 个盒子从左到右排列。第 $i$ 个盒子里有 $A_i$ 个糖果。你将从一些连续的盒子中取出糖果并平均分给 $M$ 个孩子。在这种情况下，求满足以下条件的对 $(l, r)$ 的数量：

$l$ 和 $r$ 是整数并且满足 $1 \leq l \leq r \leq N$ 。 $A_l + A_{l+1} + ... + A_r$ 是 $M$ 的倍数。

输入采用标准输入，格式如下： $N$ $M$ $A_1$ $A_2$ $...$ $A_N$

输出满足条件的对 $(l, r)$ 的数量。注意该数量可能不能装入 32 位整数类型。

3 2
4 1 5

13 17
29 7 5 7 9 51 7 13 8 55 42 9 81

10 400000000
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

输入中的所有值均为整数。 $1 \leq N \leq 10^5$ $2 \leq M \leq 10^9$ $1 \leq A_i \leq 10^9$ 每个对 $(l, r)$ 的和 $A_l + A_{l+1} + ... + A_r$ 如下：

对 $(1, 1)$ 的和： $4$ 对 $(1, 2)$ 的和： $5$ 对 $(1, 3)$ 的和： $10$ 对 $(2, 2)$ 的和： $1$ 对 $(2, 3)$ 的和： $6$ 对 $(3, 3)$ 的和： $5$

其中，有三个是 $2$ 的倍数。

标签: AtCoder|abc105D

AtCoder|abc105D