← 返回题目列表

AtCoder · abc367_d

G. 计步器

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有 N 湖边的休息区。
其余区域已编号 1, 2, ..., N 按顺时针顺序。
需要 A_i 从休息区顺时针步行的步骤 i 前往休息区 i+1 (休息区 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 is 2,它不是的倍数 3.
  • 从休息区顺时针步行的最少步数 1 前往休息区 3 is 3,它是 3.
  • 从休息区顺时针步行的最少步数 1 前往休息区 4 is 7,它不是的倍数 3.
  • 从休息区顺时针步行的最少步数 2 前往休息区 3 is 1,它不是的倍数 3.
  • 从休息区顺时针步行的最少步数 2 前往休息区 4 is 5,它不是的倍数 3.
  • 从休息区顺时针步行的最少步数 2 前往休息区 1 is 8,它不是的倍数 3.
  • 从休息区顺时针步行的最少步数 3 前往休息区 4 is 4,它不是的倍数 3.
  • 从休息区顺时针步行的最少步数 3 前往休息区 1 is 7,它不是的倍数 3.
  • 从休息区顺时针步行的最少步数 3 前往休息区 2 is 9,它是 3.
  • 从休息区顺时针步行的最少步数 4 前往休息区 1 is 3,它是 3.
  • 从休息区顺时针步行的最少步数 4 前往休息区 2 is 5,它不是的倍数 3.
  • 从休息区顺时针步行的最少步数 4 前往休息区 3 is 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