分数: 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