2089 - 休息区

Description

一个湖周围有 $N$ 个休息区。

这些休息区按顺时针顺序编号为 $1$ 、 $2$ 、......、 $N$ 。

从休息区 $i$ 顺时针走到休息区 $i+1$ 需要 $A _ i$ 步(其中休息区 $N+1$ 指的是休息区 $1$ )。

从休息区 $s$ 顺时针走到休息区 $t$ ( $s \neq t$ )所需的最小步数是 $M$ 的倍数。

求 $(s,t)$ 的可能对数。

Input

两个数字N和M

接下来一行，N个数字 $a_i$

Output

一个数字，表示步数为M倍数的对数的数量

Examples

4 3
2 1 4 3

9 5
9 9 8 2 4 4 3 5 3

Hint

样例1说明：

- 从休息区 $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)$ 。

数据范围：

- 所有输入值均为整数

- 30%的数据： $2 \le N \le 2 \times 100$

- 100%的数据： $2 \le N \le 2 \times 10^5$

- $1 \le A_i \le 10^9$

- $1 \le M \le 10^6$

题目参数

Discuss

Stats

上一题

下一题