蓝桥杯2017年第八届真题-k倍区间-题解（C++代码）

解题思路:

               1、 N 的范围上限是100,000，直接枚举 i 和 j 必然超时，所以使用前缀和将 Ai+1    +  ……   +   Aj   变为   Sj  -  Si  ,其中 Sj 为前 j 项之和；

               2、获得Sj 后，由于其本身还不能直接满足题中所有区间的条件（可以间接作差获得），再次枚举也不是很合适，尝试其他办法；

               3、题中所要求的是K的倍数，具体是什么值并不重要，所以让所有Sj 对 K 求模，把Sj 对K 余数的不同来分类 ；

               4、区间是K的倍数，前面说过，Sj 可以通过作差获得所有区间，所以答案来自两部分，一部分是本身就是K的倍数的Sj ,即A1 + ……   +   Aj  （j >=1）

                        另一部分是余数相同的Sj 两两作差，比如区间Si 与区间 Sj 对k 模数相同，则 Sj - Si 满足条件，即  Ai+1    +  ……   +   Aj （j > i >= 1）

C ²_w

注意事项:

参考代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int n,k;
typedef long long ll;
ll s[maxn],a[maxn];
int main(){
    cin>>n>>k;
    vector<int> ve[k];          //动态数组ve保存分类后的S[j]数组
    for(int i = 1;i<=n;i++){
        cin>>a[i];
        s[i]=a[i]+s[i-1];
        ll p = s[i]%k;
        ve[p].push_back(s[i]);
    }
    ll ans = ve[0].size();     // 第一部分答案
    for(int i = 0;i<k;i++){
        ll w = ve[i].size();
        if(w<=1)
            continue;
        ans += w * (w-1) / 2; // 第二部分，余数相同两两配对，从一共W个数中任取两个，有 w * (w-1) / 2 种（组合数）
    }
    cout<<ans<<endl;
    return 0;
}