G - Pedometer Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

湖の周りに N 個の休憩所があります。
休憩所には時計回りに 1,2,\dots,N の番号が付いています。
休憩所 i から休憩所 i+1 まで時計回りに歩くには A_i 歩かかります ( 但し、休憩所 N+1 は休憩所 1 を指します ) 。
休憩所 s から休憩所 t ( s \neq t ) まで時計回りに歩くのにかかる最小の歩数は M の倍数でした。
(s,t) の組として考えられるものの数を求めてください。

制約

  • 入力は全て整数
  • 2 \le N \le 2 \times 10^5
  • 1 \le A_i \le 10^9
  • 1 \le M \le 10^6

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 A_2 \dots A_N

出力

答えを整数として出力せよ。

入力例 1

4 3
2 1 4 3

出力例 1

4
  • 休憩所 1 から休憩所 2 まで時計回りに歩くのにかかる最小の歩数は 2 歩で、これは 3 の倍数ではありません。
  • 休憩所 1 から休憩所 3 まで時計回りに歩くのにかかる最小の歩数は 3 歩で、これは 3 の倍数です。
  • 休憩所 1 から休憩所 4 まで時計回りに歩くのにかかる最小の歩数は 7 歩で、これは 3 の倍数ではありません。
  • 休憩所 2 から休憩所 3 まで時計回りに歩くのにかかる最小の歩数は 1 歩で、これは 3 の倍数ではありません。
  • 休憩所 2 から休憩所 4 まで時計回りに歩くのにかかる最小の歩数は 5 歩で、これは 3 の倍数ではありません。
  • 休憩所 2 から休憩所 1 まで時計回りに歩くのにかかる最小の歩数は 8 歩で、これは 3 の倍数ではありません。
  • 休憩所 3 から休憩所 4 まで時計回りに歩くのにかかる最小の歩数は 4 歩で、これは 3 の倍数ではありません。
  • 休憩所 3 から休憩所 1 まで時計回りに歩くのにかかる最小の歩数は 7 歩で、これは 3 の倍数ではありません。
  • 休憩所 3 から休憩所 2 まで時計回りに歩くのにかかる最小の歩数は 9 歩で、これは 3 の倍数です。
  • 休憩所 4 から休憩所 1 まで時計回りに歩くのにかかる最小の歩数は 3 歩で、これは 3 の倍数です。
  • 休憩所 4 から休憩所 2 まで時計回りに歩くのにかかる最小の歩数は 5 歩で、これは 3 の倍数ではありません。
  • 休憩所 4 から休憩所 3 まで時計回りに歩くのにかかる最小の歩数は 6 歩で、これは 3 の倍数です。

以上より、求めるべき (s,t) の組の数は 4 個です。

入力例 2

2 1000000
1 1

出力例 2

0

入力例 3

9 5
9 9 8 2 4 4 3 5 3

出力例 3

11

Score : 400 points

Problem Statement

There are N rest areas around a lake.
The rest areas are numbered 1, 2, ..., N in clockwise order.
It takes A_i steps to walk clockwise from rest area i to rest area i+1 (where rest area N+1 refers to rest area 1).
The minimum number of steps required to walk clockwise from rest area s to rest area t (s \neq t) is a multiple of M.
Find the number of possible pairs (s,t).

Constraints

  • All input values are integers
  • 2 \le N \le 2 \times 10^5
  • 1 \le A_i \le 10^9
  • 1 \le M \le 10^6

Input

The input is given from Standard Input in the following format:

N M
A_1 A_2 \dots A_N

Output

Print the answer as an integer.

Sample Input 1

4 3
2 1 4 3

Sample Output 1

4
  • The minimum number of steps to walk clockwise from rest area 1 to rest area 2 is 2, which is not a multiple of 3.
  • The minimum number of steps to walk clockwise from rest area 1 to rest area 3 is 3, which is a multiple of 3.
  • The minimum number of steps to walk clockwise from rest area 1 to rest area 4 is 7, which is not a multiple of 3.
  • The minimum number of steps to walk clockwise from rest area 2 to rest area 3 is 1, which is not a multiple of 3.
  • The minimum number of steps to walk clockwise from rest area 2 to rest area 4 is 5, which is not a multiple of 3.
  • The minimum number of steps to walk clockwise from rest area 2 to rest area 1 is 8, which is not a multiple of 3.
  • The minimum number of steps to walk clockwise from rest area 3 to rest area 4 is 4, which is not a multiple of 3.
  • The minimum number of steps to walk clockwise from rest area 3 to rest area 1 is 7, which is not a multiple of 3.
  • The minimum number of steps to walk clockwise from rest area 3 to rest area 2 is 9, which is a multiple of 3.
  • The minimum number of steps to walk clockwise from rest area 4 to rest area 1 is 3, which is a multiple of 3.
  • The minimum number of steps to walk clockwise from rest area 4 to rest area 2 is 5, which is not a multiple of 3.
  • The minimum number of steps to walk clockwise from rest area 4 to rest area 3 is 6, which is a multiple of 3.

Therefore, there are four possible pairs (s,t).

Sample Input 2

2 1000000
1 1

Sample Output 2

0

Sample Input 3

9 5
9 9 8 2 4 4 3 5 3

Sample Output 3

11