K倍 区间 前缀和+思维

题目
思路：我做的时候用的复杂度是n2，但是可以优化，既然是区间和，可以只要保证让前面的数modK和后面的数modK相等就能保证该区间能被整除

#include<iostream>
using namespace std;
const   int N=100010;
long long a[N],cnt[N],sum[N];//坑题，会爆int int main()
{
   
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<=n;i++)
    sum[i]=sum[i-1]+a[i];
   long long res=0;
    for(int i=0;i<=n;i++)
    {
   
       res+=cnt[sum[i]%k]; 
        cnt[sum[i]%k]++;
    }
    printf("%lld\n",res);
}
    
}