101053: [AtCoder]ABC105 D - Candy Distribution

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $400$ points

Problem Statement

There are $N$ boxes arranged in a row from left to right. The $i$-th box from the left contains $A_i$ candies.

You will take out the candies from some consecutive boxes and distribute them evenly to $M$ children.

Such being the case, find the number of the pairs $(l, r)$ that satisfy the following:

  • $l$ and $r$ are both integers and satisfy $1 \leq l \leq r \leq N$.
  • $A_l + A_{l+1} + ... + A_r$ is a multiple of $M$.

Constraints

  • All values in input are integers.
  • $1 \leq N \leq 10^5$
  • $2 \leq M \leq 10^9$
  • $1 \leq A_i \leq 10^9$

Input

Input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $A_2$ $...$ $A_N$

Output

Print the number of the pairs $(l, r)$ that satisfy the conditions.

Note that the number may not fit into a $32$-bit integer type.

Sample Input 1

3 2
4 1 5

Sample Output 1

3

The sum $A_l + A_{l+1} + ... + A_r$ for each pair $(l, r)$ is as follows:

  • Sum for $(1, 1)$: $4$
  • Sum for $(1, 2)$: $5$
  • Sum for $(1, 3)$: $10$
  • Sum for $(2, 2)$: $1$
  • Sum for $(2, 3)$: $6$
  • Sum for $(3, 3)$: $5$

Among these, three are multiples of $2$.

Sample Input 2

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

Sample Output 2

6

Sample Input 3

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

Sample Output 3

25

Input

题意翻译

有 $n$ 个盒子排成一排，其中左数第 $i$ 个盒子里面有 $a_i$ 个气球。你现在需要从一段连续的盒子当中取出所有的糖果，然后均匀地分给 $m$ 个小朋友。你希望最终每个小朋友手上的糖果数量相同，因此，你思考着有多少组连续的盒子里面的糖果数量是 $m$ 的倍数。形式化地说，你想找到一共有多少个二元组 $(l,r)$ 满足如下要求： - $1\leqslant l\leqslant r\leqslant n$。 - $\sum\limits_{i=l}^r a_i\mid m$。 数据范围： - $1\leqslant n\leqslant 10^5$，$2\leqslant m\leqslant 10^9$。 - $1\leqslant a_i\leqslant 10^9$。 Translated by Eason_AC 2021.12.27

Source/Category

加入题单

算法标签：