k倍区间 | 前缀和

k倍区间 - 蓝桥云课 (lanqiao.cn)

 1 #include<iostream>
 2 using namespace std;
 3 #define ios_base \
 4     ios::sync_with_stdio(false);\
 5     cin.tie(nullptr);\
 6     cout.tie(nullptr)
 7 const int N = 1e5+10;
 8 int n,k;//cnt[]用来计数不同余数的出现次数
 9 long long a[N],cnt[N];//cnt[]的下标可不只有0~9这么简单，举个例子：999%9999，保险起见还是开long long cnt[],而a[]要作为前缀和数组所以也要开大点
10 long long res=0;
11 int main()
12 {
13     ios_base;
14     cin>>n>>k;
15     for (int i = 1; i <= n; i++)
16     {
17         cin>>a[i];
18         a[i]+=a[i-1];//构建前缀和数组
19     }
20     cnt[0]++;
21     for (int i = 1; i <= n; i++)
22     {
23         res+=cnt[a[i]%k];
24         cnt[a[i]%k]++;
25     }
26     cout<<res<<'\n';
27 
28     return 0;
29 }