103673: [Atcoder]ABC367 D - Pedometer
Description
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
Output
得分：400分
问题陈述
湖周围有$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