问题 P: 倍数区间
传统题
1.000s
时间限制
256MB
内存限制
29 提交
23 解决
【题目描述】
题目描述
给定一个数列 a1
,a2,…,an
，若有一个区间 [L,
R]
满足
a
l+a
l+1+
...+a
r−1+a
r
为 k 的倍数，则称[L,
R]
为k的倍数区间 。
给定k，请统计在给定的数列中，有多少个区间是 k 的倍数区间。
输入格式
第一行：两个整数 n 与 k；
第二行：n 个整数 a1,…,an
。
输出格式
单个整数：表示倍数区间的数量。
数据范围
对于 30% 的数据，n≤200
；
对于 60% 的数据，n≤5000
；
对于 100% 的数据，1≤n≤200000
；
1≤k≤100000
，0≤ai≤10000
。
样例数据
输入:
4 20
30 20 40 10
输出:
4
说明:
满足要求的区间有：[20],[40],[20,40],[30,20,40,10]