题目描述

给定一个长度为 N 的数列，A1,A2,…AN，如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。

你能求出数列中总共有多少个 K 倍区间吗？

输入格式

第一行包含两个整数 N 和 K。

以下 N 行每行包含一个整数 Ai。

输出格式

输出一个整数，代表 K 倍区间的数目。

数据范围

1≤N,K≤100000,
1≤Ai≤100000

输入样例：

5 2
1
2
3
4
5

输出样例：

6

解题思路

暴力枚举 $O(n^3)$ ——> 双重循环 + 前缀和 $O(n^2)$ ——> 内层循环等价变形 + 前缀和 $O(n)$

暴力枚举 $O(n^3)$

long long res = 0;
for(int r = 1; r <= n; r ++){
    for(int l = 1; l <= r; l ++){
        long long sum = 0;
        for(int i = l; i <= r; i ++){
            sum += a[i];
            if(sum % k == 0) res ++;
        }
    }
}

双重循环 + 前缀和 $O(n^2)$

long long res = 0;
for(int r = 1; r <= n; r ++){
    for(int l = 1; l <= r; l ++){
        if((sum[r] - s[l - 1])) % k == 0) res ++;
    }
}

内层循环等价变形 $O(n)$

long long res = 0;
for(int r = 1; r <= n; r ++){
    for(int l = 1; l <= r; l ++){
        if((sum[r] - s[l - 1])) % k == 0) res ++;
    }
}
内层循环：
for(int l = 1; l <= r; l ++){
        if((sum[r] - s[l - 1])) % k == 0) res ++;
    }
内层循环的含义：
在1 ~ r之间，有多少个l满足 sum[r] - s[l - 1] % k == 0
亦即在0 ~ r - 1之间有多少个l满足 sum[r] - s[l] % k == 0
亦即在0 ~ r - 1之间有多少个l满足 sum[r] % k 与 sum[l] % k相等

cnt[i]表示余数是i的个数有多少个
cnt[sum[r] % k] 表示余数是sum[r] % k 有多少个,亦即余数是sum[l] % k 的l有多少个
res表示k倍区间的个数

long long res = 0;
cnt[0] = 1;
for(int r = 1; r <= n; r ++){
    res += cnt[sum[r] % k];
    cnt[sum[r] % k] ++;
}

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 100010;

int n, k;
LL s[N], cnt[N];// cnt[i]表示余数是i的个数有多少个

int main(){
    scanf("%d%d", &n, &k);

    for(int i = 1; i <= n; i ++){
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }

    LL res = 0;
    cnt[0] = 1;//在循环之前s[0] % k = 0的个数已经有一个了,所以cnt[0] = 1
    for(int r = 1; r <= n; r ++){
        res += cnt[s[r] % k];
        cnt[s[r] % k] ++;
    }

    printf("%lld\n", res);

    return 0;

}