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

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define endl '\n'
#define aaa; for(ll i=1;i<=n;i++)cout<<a[i]<<' ';
const ll N=1e5+5;
ll n,k,a[N];
ll p[N],kkk;//p数组表示每个余数能形成的区间数
int main(){
    fill(p,p+N,-1);//初始化p数组为-1，因为一个余数无法形成区间
    cin>>n>>k;
    for(ll i=1;i<=n;i++){
       cin>>a[i];
       a[i]=(a[i]+a[i-1])%k;//前缀和取余
    }
    //aaa;
    p[0]=0;//初始化p[0]为0，因为0余数之前的全部能形成区间
    for(ll i=1;i<=n;i++){
       p[a[i]]++;//每出现一次该余数，p[余数]++
       kkk+=p[a[i]];//统计区间数
    }
    cout<<kkk<<endl;
    return 0;
}