一看这种求和的果断前缀和
然后设了K作为边界,那么我们只考虑所有前缀和余K后剩下的数
比如题目所给的样例:
5 2
1 2 3 4 5
我们求一次前缀和
得:
1 3 6 10 15
求余数以后:
1 1 0 0 1
那么我们可以看到,余数相同的,只要减去余数(前后相减),不就是K的倍数了么(将余数减没)…
然后对于0我们特判一次
因为我们0可以只拿一次,不一定拿两个区间
#include <iostream>
using namespace std;
typedef long long ll;
ll C(ll m)
{
return m*(m-1)/2;
}
int main()
{
int n,k;
scanf("%d %d",&n,&k);
ll sum[n+1];
sum[0] = 0;
int all[k] = {0};
for(int i=0;i<n;i++)
{
int x;
scanf("%d",&x);
sum[i+1] = sum[i] + x;
sum[i+1]%=k;
all[sum[i+1]]++;
}
long long ans = 0;
//可以直接选这一块的
ans += all[0];
//或者从中挑选2块
ans += C(all[0]);
for(int i=1;i<k;i++)//那只能是相同余数的了
ans += C(all[i]);
cout<<ans;
return 0;
}