题目描述

给定长度为 $N$ 的数组 $A$，求有多少个连续区间 $(l, r)$，满足区间和是 $K$ 的倍数。

数据范围：$1 \le N, K \le 10^5$，$1 \le A_i \le 10^5$。

题面：洛谷 P8649 [蓝桥杯 2017 省 B] k 倍区间

一、思路：前缀和 + 同余

1.1 前缀和

定义前缀和数组 $s$，规定：

区间 $(l, r)$ 的总和：

1.2 题目条件 → 同余关系

题目要 "区间和是 $K$ 的倍数"：

等价变形：

核心结论：只要两个前缀和对 $K$ 取模的余数相等，它们之间的区间和就一定是 $K$ 的倍数。

1.3 直观例子

$K = 2$，$s[r] = 15$，$s[l-1] = 3$：

  • $15 \bmod 2 = 1$，$3 \bmod 2 = 1$ → 余数相同 ✔
  • $s[r] - s[l-1] = 12$，12 是 2 的倍数 ✔

所以数"前缀和同余对数"就是答案。

二、暴力思路（仅用于理解）

固定左右端点枚举所有区间：

$N = 10^5$ 时复杂度 $O(N^2)$，必然超时。

三、思路：桶计数

把所有 $s[i]$ 对 $K$ 取模，余数范围是 $[0, K-1]$。同余的前缀和可以两两配对——任意两个余数相同的前缀和都能形成一个合法的 $K$ 倍区间。

桶计数：开一个大小为 $K$ 的数组 cnt，cnt[r] 表示「到目前为止，前缀和模 $K$ 等于 $r$ 的出现次数」。

  • 遍历到前缀和 s[i] 时，先把它和前面 cnt[rem] 个同余前缀和配对；
  • 然后把 cnt[rem]++，把自己加入桶里供后续元素配对。

特别地，cnt[0] = 1，因为 s[0] = 0 这个虚前缀和一开始就在桶里——这处理了"从数组开头开始的区间"。

四、版本 1：分两步写（易读）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
    int n, k;
    cin >> n >> k;
    vector<ll> s(n + 1, 0);

    // 第一步：读入 + 计算前缀和
    for (int i = 1; i <= n; i++) {
        ll x; cin >> x;
        s[i] = s[i - 1] + x;
    }

    // 第二步：统计同余配对
    vector<ll> cnt(k, 0);
    cnt[0] = 1;                       // s[0] = 0 占位
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        int rem = s[i] % k;
        ans += cnt[rem];              // 当前 s[i] 与前面 cnt[rem] 个前缀和配对
        cnt[rem]++;                   // 自己入桶，供后续元素配对
    }
    cout << ans;
    return 0;
}

代码解释

  1. s 数组：s[i] 保存前 $i$ 个数总和，s[0] = 0 是必不可少的初始项。
  2. cnt[0] = 1：把 $s[0]$ 预先放进桶，对应"从数组头开始的合法区间"。
  3. 遍历每个前缀和余数：ans 加上桶里同余数的数量；然后把当前余数入桶。

配对原理：若余数 $r$ 已经出现 $m$ 次，则当前这个前缀和可以和前面 $m$ 个前缀和配成 $m$ 个新区间。

五、版本 2：单循环压缩（竞赛推荐）

其实不需要保存全部前缀和——只用一个变量 sum 持续累加，省掉 $O(N)$ 内存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
    int n, k;
    cin >> n >> k;
    vector<ll> cnt(k, 0);
    cnt[0] = 1;
    ll sum = 0, ans = 0;

    // 只一层循环：边读入，边累加前缀和，边统计
    for (int i = 1; i <= n; i++) {
        ll x; cin >> x;
        sum += x;                     // 当前前缀和
        int rem = sum % k;            // 当前前缀和对 k 取模
        ans += cnt[rem];              // 累加可以配对的区间数量
        cnt[rem]++;                   // 自己入桶
    }
    cout << ans;
    return 0;
}

压缩版要点

  • 删掉了存储全部前缀和的 s 数组，只用 sum 保存当前前缀和；
  • 数学上和版本 1 完全等价，只是把"先求全部前缀和，再统计"合并成"边读边做"；
  • 内存从 $O(N)$ 降到 $O(K)$，代码更短。

⚠️ 必看的坑

坑 说明
ans 必须 long long 区间数量可能很大，int 必溢出
cnt 也建议 long long 防止计数溢出
cnt 大小是 $K$ $0 \le \text{rem} < K$
rem = sum % k 在 C++ 里负数取模可能为负 题目保证 $A_i > 0$，sum 一直正，没问题

六、样例手算

输入：

1
2
3
4
5
6
5 2
1
2
3
4
5

初始：sum = 0, ans = 0, cnt[0] = 1, cnt[1] = 0

i x sum rem ans += cnt[rem] cnt[rem]++
1 1 1 1 ans += 0 = 0 cnt[1]=1
2 2 3 1 ans += 1 = 1 cnt[1]=2
3 3 6 0 ans += 1 = 2 cnt[0]=2
4 4 10 0 ans += 2 = 4 cnt[0]=3
5 5 15 1 ans += 2 = 6 cnt[1]=3

ans = 6 ✔

七、复杂度对比

解法 时间 空间
暴力枚举 $l, r$ $O(N^2)$（超时） $O(1)$
前缀和 + 桶（版本 1） $O(N)$ $O(N + K)$
前缀和 + 桶（版本 2，压缩） $O(N)$ $O(K)$

八、易错点清单

  1. ans 用 int：$N = 10^5$ 时区间数可达 $\sim 10^{10}$，int 溢出 → 必须 long long。
  2. 忘 cnt[0] = 1：漏掉就漏掉所有从数组头开始的合法区间。
  3. 负数取模：sum % k 在 sum 可能为负时得到负数，C++ 里要 ((sum % k) + k) % k。本题 $A_i > 0$，不用处理。
  4. cnt 大小开错：必须是 $K$，不是 $N$。
  5. 写成 $O(N^2)$ 暴力：必超时。

九、小结

  • 核心：区间和是 $K$ 倍数 $\iff$ 两端前缀和对 $K$ 同余；
  • 算法：前缀和 + 同余桶计数，时间 $O(N)$；
  • 先用版本 1 写明白，再压成版本 2——比赛里直接写版本 2 即可；
  • 口诀：前缀和同余，区间 K 倍数；桶计余数次，边读边统计。