acwing 1230 K倍区间

题意

给定长度为n的数列，求出连续序列和为k的倍数的序列个数。

思路

首先，对于每一段前缀和都进行对k取余。

那么根据同余定理，,如果一段前缀和如果和前面的某段前缀和的值相同，那么前面的那个前缀所缺少的几个数（除最后一个元素）的和一定是k的倍数，对于每个余数所对应的前缀和数量，用一个map记录一下即可。

最后记得再加上，因为每次前缀和所得的那几个数并不包括尾部，所以当遍历到最后一个元素时，并无法得出包括最后一个元素的符合条件的连续序列数量，而是包括最后一个前面的那个元素的符合条件的连续序列数量。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
const int N=1e5+10;
typedef pair<int,int>pp;
void solve()
{
    int n,k;
    cin>>n>>k;
    vector<int>a(n+1);
    for(int i=1;i<=n;++i)cin>>a[i];
    vector<int>sum(n+1);
    map<int,int>mp;
    int ans=0;
    for(int i=1;i<=n;++i){
        sum[i]=(sum[i-1]+a[i])%k;
        ans+=mp[sum[i]];
        mp[sum[i]]++;
    }
    cout<<mp[0]+ans<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    // cin>>T;
    while(T--)	solve();
    return 0;
}