题目描述:
给定一个长度为 N的数列,A1,A2,…AN,如果其中一段连续的子序列 Ai,Ai+1,…Aj之和是 K 的倍数,我们就称这个区间 [i,j] 是 K 倍区间。
你能求出数列中总共有多少个 K 倍区间吗?
输入格式
第一行包含两个整数 N 和 K。
以下 N 行每行包含一个整数 Ai。
输出格式
输出一个整数,代表 K 倍区间的数目。
数据范围
1≤N,K≤100000,
1≤Ai≤100000
输入样例:
5 2
1
2
3
4
5
输出样例:
6
/*
计算前缀和,枚举右端点,求区间和模k的值相等的条件等价于
Si-Si-1 取余 k 等于0
Si-Si-2 取余 k 等于0
……
Si-S0 取余 k 等于0
即Si 取余k的值等于 S0 S1 …… Si-1 取余k的值
因此每次遍历到第i个元素的时候只需将答案加上与S[i]取余k的值相同的个数
*/
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const int MAX = 100009;
int n, k;
LL s[MAX];
int cnt[MAX];
LL ans;
int main()
{
scanf("%d%d", &n, &k);
cnt[0] ++;
for(int i = 1; i <= n; i++)
{
scanf("%lld", &s[i]);
s[i] += s[i - 1];
ans += cnt[s[i] % k];
cnt[s[i] % k] ++;
}
printf("%lld\n", ans);
return 0;
}