分数: 400 点
问题陈述
有 N 框从左到右排列成一排。的 i左边第一个框包含 A_i 糖果。
你将从一些连续的盒子中取出糖果,并将它们均匀地分发给 M 孩子们。
既然如此,求对的个数 (l, r) 满足以下条件:
- l 和 r 都是整数并且满足 1 \leq l \leq r \leq N.
- A_l + A_{l+1} + ... + A_r 是的倍数 M.
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 10^5
- 2 \leq M \leq 10^9
- 1 \leq A_i \leq 10^9
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 ... A_N
输出
打印对数 (l, r) 满足条件。
请注意,该数字可能不适合 32- 位整数类型。
示例输入 1
3 2 4 1 5
示例输出 1
3
总和 每对 A_l + A_{l+1} + ... + A_r 对于每对 (l, r) 如下:
- 总和 (1, 1): 4
- 总和 (1, 2): 5
- 总和 (1, 3): 10
- 总和 (2, 2): 1
- 总和 (2, 3): 6
- 总和 (3, 3): 5
其中,3是的倍数 2.
示例输入 2
13 17 29 7 5 7 9 51 7 13 8 55 42 9 81
示例输出 2
6
示例输入 3
10 400000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
示例输出 3
25