[//]: # 写给自己看的

K倍区间

include [HTML_REMOVED]

using namespace std;
const int N=100010;
typedef long long LL;
int n,K;
LL a[N];
LL b[N];
LL cnt[N];
int main(){
cin>>n>>K;
LL res=0;
for(int i=1;i<=n;i){
scanf(“%d”,&a[i]);
b[i]=a[i]+b[i-1];
cnt[b[i]%K];
}
for(int i=1;i<K;i++){
if(cnt[i]==2){
res+=1;
}
else if(cnt[i]==0){

    }
    else {
        res+=(cnt[i])*(cnt[i]-1)/2;//不是(cnt[i]-1)*(cnt[i]-2)/2因为相当于排列组合Cn2
}

}
res+=cnt[0]*(cnt[0]-1)/2+cnt[0];
cout<<res<<endl;
return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla