← 返回题目列表

AtCoder · abc105_d

D. 糖果分发

中文机器翻译题面 查看原题

分数: 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