D - お菓子の分配 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は、 N 個のお菓子が一列に並んでいる箱を持っています。左から i 番目のお菓子の重さは A_i グラムです。

高橋君は、この箱から連続して並んでいる 1 個以上のお菓子を選んで袋に詰め、 K 人の友達にプレゼントしようと考えています。友達全員に同じ重さずつ配りたいので、選んだお菓子の重さの合計が K グラムの倍数である必要があります。

連続して並んだ 1 個以上のお菓子の選び方であって、選んだお菓子の重さの合計が K の倍数となるものが何通りあるか求めてください。ただし、選んだお菓子の範囲（開始位置または終了位置）が異なれば、重さの合計が同じであっても異なる選び方として数えます。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数である

入力

N K
A_1 A_2 \ldots A_N
  • 1 行目には、お菓子の個数 N と、友達の人数 K が、スペース区切りで与えられる。
  • 2 行目には、各お菓子の重さ A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

選んだお菓子の重さの合計が K の倍数となるような、連続する 1 個以上のお菓子の選び方の個数を 1 行で出力してください。

入力例 1

5 3
1 2 3 1 2

出力例 1

7

入力例 2

8 5
2 3 5 1 4 2 3 5

出力例 2

16

入力例 3

10 1000000000
500000000 500000000 300000000 700000000 100000000 900000000 400000000 600000000 200000000 800000000

出力例 3

15

Score : 400 pts

Problem Statement

Takahashi has a box containing N sweets lined up in a row. The weight of the i-th sweet from the left is A_i grams.

Takahashi wants to select one or more consecutive sweets from this box, pack them into a bag, and give them as a present to his K friends. Since he wants to distribute the sweets equally by weight to all his friends, the total weight of the selected sweets must be a multiple of K grams.

Find the number of ways to select one or more consecutive sweets such that the total weight of the selected sweets is a multiple of K. Note that if the ranges of selected sweets differ (i.e., the starting position or ending position differs), they are counted as different selections even if the total weights are the same.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq A_i \leq 10^9
  • All input values are integers.

Input

N K
A_1 A_2 \ldots A_N
  • The first line contains the number of sweets N and the number of friends K, separated by a space.
  • The second line contains the weights of each sweet A_1, A_2, \ldots, A_N, separated by spaces.

Output

Print in one line the number of ways to select one or more consecutive sweets such that the total weight of the selected sweets is a multiple of K.

Sample Input 1

5 3
1 2 3 1 2

Sample Output 1

7

Sample Input 2

8 5
2 3 5 1 4 2 3 5

Sample Output 2

16

Sample Input 3

10 1000000000
500000000 500000000 300000000 700000000 100000000 900000000 400000000 600000000 200000000 800000000

Sample Output 3

15