Pedometer

题目描述

湖周围有 $N$ 个休息区。
休息区按照顺时针方向编号为 $1, 2, \dots, N$.
从休息区 $i$ 顺时针走到休息区 $i+1$（其中休息区 $N+1$ 指休息区 $1$）需要 $A_i$ 步。
从休息区 $s$ 到休息区 $t$（$s \neq t$）顺时针行走所需的最少步数是 $M$ 的倍数。
可能的有序对 $(s,t)$ 的个数是多少？

输入格式

输入由标准输入给出，格式如下： $N$ $M$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出一个整数，表示答案。

4 3
2 1 4 3

4

2 1000000
1 1

0

9 5
9 9 8 2 4 4 3 5 3

11

提示

所有输入值均为整数 $2 \le N \le 2 \times 10^5$ $1 \le A_i \le 10^9$ $1 \le M \le 10^6$从休息区 $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)$ 有四个。

标签: AtCoder|abc367D

来源

AtCoder|abc367D