5095：果园
文件提交：无需freopen
内存限制：512 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：1
解决：0
题目描述
# 果园
## 题目描述
在一个阳光明媚的村庄里，小 $A$ 有一片美丽的果园。
果园里种着一排果树，这些果树从左到右依次排列，共有 $N$ 棵。每棵果树上都结了许多果实，第 $i$ 棵果树上结了 $A_i$ 个果子。
小明计划在丰收的季节里，从这些果树中挑选一段连续的树，将收获的果子分给村里的 $M$ 个小伙伴。他希望每个小伙伴都能**分到同样数量的果子**，因此他需要选择一段连续的果树，使得**这些树上果子的总数是 $M$ 的倍数**。
具体来说，小明需要找到所有可能的区间 $[L, R]$ ，满足以下条件：
- $1 \leq L \leq R \leq N$ ，其中 $N$ 是果树的数量。
- 从第 $L$ 棵果树到第 $R$ 棵果树（包含第 $L$ 棵和第 $R$ 棵）的果子总数 $A_L + A_{L+1} + \dots + A_R$ 是 $M$ 的倍数。
你的任务是帮助小明计算出，共有多少个这样的区间 $[L, R]$ 满足条件。
## 输入格式
第一行包含两个整数 $N$ 和 $M$ ，分别表示果树的数量和村里小伙伴的数量。
第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$ ，表示每棵果树上的果子数量。
## 输出格式
输出一个整数，表示满足条件的区间 $[L, R]$ 的总数。
## 样例
### 样例输入 1
```text
3 2
4 1 5
```
### 样例输出 1
```text
3
```
### 样例输入 2
```text
13 17
29 7 5 7 9 51 7 13 8 55 42 9 81
```
### 样例输出 2
```text
6
```
### 样例输入 3
```text
40 6
1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 2 1 1 4 1 5 1 5
```
### 样例输出 3
```text
154
```
## 说明/提示
样例 $1$ 说明
果园有 3 棵果树，果子数量分别为 4、1、5，小伙伴数量为 2。小明需要找到所有连续的果树区间，使得这些树上的果子总数是 2 的倍数。
具体分析如下：
- 区间 $[1, 1]$ ：只有第 1 棵树，果子总数 $4$ ，是 2 的倍数。
- 区间 $[1, 2]$ ：第 1 到第 2 棵树，果子总数 $4 + 1 = 5$ ，不是 2 的倍数。
- 区间 $[1, 3]$ ：第 1 到第 3 棵树，果子总数 $4 + 1 + 5 = 10$ ，是 2 的倍数。
- 区间 $[2, 2]$ ：只有第 2 棵树，果子总数 $1$ ，不是 2 的倍数。
- 区间 $[2, 3]$ ：第 2 到第 3 棵树，果子总数 $1 + 5 = 6$ ，是 2 的倍数。
- 区间 $[3, 3]$ ：只有第 3 棵树，果子总数 $5$ ，不是 2 的倍数。
因此，满足条件的区间有 $[1, 1]$ 、 $[1, 3]$ 、 $[2, 3]$ ，总数为 3。
数据范围
对于 $10\%$ 的数据，满足 $1 \le N \le 100$ ， $1 \le M \le 10$ 。
对于另外 $25\%$ 的数据，满足 $1 \le N \le 10^5$ ， $1 \le M \le 9$ 。
对于 $100\%$ 的数据，满足 $1 \leq N \leq 10^5$ ， $2 \leq M \leq 10^9$ ， $1 \leq A_i \leq 10^9$ 。
---
**题目来源：** 25年3月-C组（大咖）