蓝桥杯2017年第八届真题-k倍区间

求前缀和a[ ]，各自对K取模，若是a[i] == 0，代表他自身就符合条件，ans++，这是答案的一部分；

若取模后 != 0，则将相同的模分类计数，在相同模的前缀中任意选两个位置相减即满足条件，

所以另一部分答案为：在m个相同模的前缀和中能选出多少个两两组合（i < j）；

如输入5   2

1 2 3 4 5

那前缀和就是1 3 6 10 15

3和15除于2都余1，那么为什么15会余下一个1呢？是因为前面加了一个会余下1的数，如3所以当15舍去3之后==12满足条件 -> 从a1连加到a4==12除于2余数为0

参考代码:

#include<iostream>
#include<map>
using namespace std;
int n, k;
long long ans;
int c[100005];
int a[100005];
map<int, int> mp;
long long f(long long x){
    return (x * (x - 1)) / 2;
}
int main(){
    cin>>n>>k;
    for(int i = 1; i <= n; i++){
        cin>>c[i];
        a[i] = (a[i - 1] + c[i]) % k;
        mp[a[i]]++;
        if(a[i] == 0){
            ans++;
        }
    }
    for(map<int, int>::iterator it = mp.begin(); it != mp.end(); it++){
        ans += (long long)f(it->second);
    }
    cout<<ans;
    return 0;
}