题目1882:蓝桥杯2017年第八届真题-k倍区间

#include<iostream>
using namespace std;
int n,k;
int sum[100001];
int A[100001];
int num[100001];//统计各余数出现次数
long long cnt=0;
int main(){
    cin>>n>>k;
    num[0]=1;//有的数字本身就是k的倍数 
    for(int i=1;i<=n;i++){
        cin>>A[i];
        sum[i]=(sum[i-1]+A[i])%k;
        num[sum[i]]++;//统计相同余数的个数 
    }
    for(int i=0;i<k;i++){
        cnt+=(long long)num[i]*(num[i]-1)/2;
    } 
    cout<<cnt<<endl;
    return 0;
}