1230. K倍区间

推导过程:

前缀和数组：s[0 ~ n]
计算任意一端区间[l, r] (l, r属于[1 ~ n]) 的和使用公式s[r] - s[l - 1]
设l - 1 = t
本题要枚举r，res += s[t] (t 属于0 ~ r - 1)内的和s[r] 模k同余的数的个数
所以开一个cnt数组记一下
加完之后，再令cnt[s[r] % k] ++;

#include<iostream>
using namespace std;

const int N = 100010;

int n, k;
int a[N], s[N], cnt[N];

/*
l, r
(s[r] - s[l - 1]) % k == 0 
<=> s[r]和s[l - 1] 在mod k的意义下相等
<=> s[r] % k = s[l - 1] % k

l - 1 范围：[0, n - 1]
r范围：[1, n]
*/

int main(){
    cin >> n >> k;
    
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) s[i] = s[i - 1] + a[i];
    
    int res = 0;
    
    cnt[0] = 1; // s[0] = 0, 所以一开始mod k = 0 的前缀和有一个
    
    for(int r = 1; r <= n; r ++)
        res += cnt[s[r] % k] ++;
    
    cout << res;
    
    return 0;
}