问题 BE: 倍数区间
传统题
1.000s
时间限制
256MB
内存限制
62 提交
20 解决
【题目描述】
给定一个数列 a1,…,an，若有一个区间 [l,r] 满足
a
l+a
l+1+
...+ar-2+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。
【样例说明】
说明:
满足要求的区间有：[20],[40],[20,40],[30,20,40,10]