题目描述
blablabla
样例
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
LL a[N],s[N];
int n,k;
LL cnt[N];
int sum;
int main(){
cin >> n >> k;
//得到前缀和数组
for(int i = 1 ; i<=n ; i++){
cin >> a[i];
s[i] = s[i-1] + a[i];
}
//判断区间个数
// for(int i =1;i<=n;i++){
// for(int j=i;j<=n;j++){
// sum = s[j]-s[i-1];
// if(sum % k == 0){ //此时sum[r] % k 和 sum[l-1] % k 的余数必然也相等
// cnt ++;
// }
// }
// }
// sum[r] % k 和 sum[l-1] % k 的余数如果相等,那么sum[r] - sum[l-1]的差值必然是k的倍数
// 比如说13 % 7 和 20 % 7 (20-13)%7 =0
LL res = 0;
cnt[0] = 0; //余数为0就表示这个连续区间本来就是K倍区间,不需要再找一个端点 其前缀和%K之后余数为0.所以要先把cnt[0]置为1 当找到某个余数为0时 res直接加上就ok
for(int i =1; i<=n ; i++){
//左端点L前缀和与右端点R前缀和%m时值相等 这时表明[L,R]连续区间是K的倍数 res要加上1.
res += cnt[s[i] % k]; //初始时cnt数组都为0
cnt[s[i] % k] ++ ; // 两个相等的前缀和就能组成一个k倍区间
}
if (cnt[0] > 0) res += cnt[0];
cout << res;
return 0;
}