K倍区间

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
typedef long long ll;
int sum[N],a[N],res[N];
int n,k;
ll ans=0;
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=(sum[i-1]+a[i])%k;//前缀和取模
        ans+=res[sum[i]];//更新答案  
        //对于这个有问题的同学可以参见下面的评论 佐以理解
        res[sum[i]]++;//两个相等的前缀和就能组成一个k倍区间
    }
    cout<<ans+res[0]<<endl;
    return 0;
}

1230. K倍区间 - AcWing题库
原文链接: https://www.cnblogs.com/sherkevin/p/15812961.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍