K倍区间
此题难点在于如何求出每个点与点之间的距离，这个问题可以进行转化，如果(a[r]-a[l-1])%k==0，那么a[r]%k==a[l-1]%k;
#include<iostream>
using namespace std;
const int N=100010;
long long a[N],b[N],c,res[N];
int main()
{
int n,k;
cin>>n>>k;
long long ans=0;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=(a[i]+b[i-1]);//也可以写成b[i]=(a[i]+b[i-1])%k;就可以把long long b[N]改为int b[N];
c=b[i]%k;
ans+=res[c];
res[c]++;
}
cout<<ans+res[0];//加上0 单独出现的次数
}
查看15道真题和解析