P8649 [蓝桥杯 2017 省 B] k 倍区间 题解

· · 题解

每次取这个数组的前缀和与 k 取模，并加上这个前缀和出现的次数。如果不止一次出现，那么上一次出现的位置到这一次出现的位置之间的数的和就一定可以被 k 整除，即为 k 倍区间。

另外，如果这个前缀和已经可以直接被 k 整除的话，也算 k 倍区间。

输出最后的个数即可。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100010;
int s[N],a[N];
map<int,int>mp;
signed main()
{
    int n,k,ans=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=(s[i-1]+a[i])%k;
        ans+=mp[s[i]];
        mp[s[i]]++;
    }
    cout<<ans+mp[0];
}