acwig1230. K倍区间

题目

题解

这里cnt[i]用来表示模k的余数为i的个数，当s左右区间的余数都为i的时候，那么此时两个左右区间的之差就为0，就为K的倍数。

#include<iostream>
using namespace std;
const int N=100010;
long long s[N],cnt[N];
int n,k;
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        scanf("%lld",&s[i]);
        s[i]+=s[i-1];   
    }
    long long ans=0;
    cnt[0]=1;
    for(int i=1;i<=n;i++){
        ans+=cnt[s[i]%k];
        cnt[s[i]%k]++;
    }
    cout<<ans<<endl;
    
    return 0;
}