103673: [Atcoder]ABC367 D - Pedometer

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

问题陈述

湖周围有$N$个休息区。
休息区按顺时针方向编号为$1$、$2$、...、$N$。
从休息区$i$顺时针走到休息区$i+1$需要$A_i$步（其中休息区$N+1$指的是休息区$1$）。
从休息区$s$顺时针走到休息区$t$所需的最小步数是$M$的倍数（$s \neq t$）。
找出可能的$(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)$对。

示例输入2

2 1000000
1 1

示例输出2

0

示例输入3

9 5
9 9 8 2 4 4 3 5 3

示例输出3

11