AT_abc105_d [ABC105D] Candy Distribution

题目描述

有 $N$ 个箱子从左到右排成一列，第 $i$ 个箱子里有 $A_i$ 个糖果。

你想从若干连续的箱子中取出糖果，并将它们平均分给 $M$ 个孩子。

请你计算满足以下条件的所有组 $(l, r)$ 的总数：

• $l, r$ 都是整数，且满足 $1 \leq l \leq r \leq N$。
• $A_l + A_{l+1} + \cdots + A_r$ 是 $M$ 的倍数。

输入格式

输入通过标准输入按以下格式给出。

$N$ $M$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

输出满足条件的组 $(l, r)$ 的总数。

请注意，输出结果可能超出 $32$ 位整数范围。

样例 1

输入

3 2
4 1 5

输出

3

样例 2

输入

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

输出

6

样例 3

输入

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

输出

25

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq N \leq 10^5$
• $2 \leq M \leq 10^9$
• $1 \leq A_i \leq 10^9$

样例解释 1

对于每组 $(l, r)$，其和 $A_l + A_{l+1} + \cdots + A_r$ 如下，其中有 $3$ 组是 $2$ 的倍数。

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

由 ChatGPT 4.1 翻译