前缀和技术实战：从乘积到整除子数组

二、问题转用前缀和

1. 模减消实质

利用同余性质简化计算：(a + p*k) % p = a % p。

2. 同余定理

若差被整除 (a - b) % p == 0，则 a % p == b % p。

2.1 证明

(a - b) / p = k
=> a - b = p * k
=> a = b + p * k
=> a % p = (b + p * k) % p
=> a % p = b % p

3. 取模%

3.1 计算机行为

3.1.1 向零取整 相除

余数绝对值最接近 0 地相除。

3.1.2 符号

同被除数。

3.2 数学定义

3.2.1 向下取整 相除

余数正值最接近 0 地相除。

3.2.2 符号

正数。

3.3 两者关系

3.3.1 差异

只有 负 % 正 的负数取模时 结果会不同（计算机为负、数学为正）。

3.3.2 转化

计算机 相同等效、不同转化 为 数学 的模结果：(a % p + p) % p。

public int subarraysDivByK(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    int sum = 0, ret = 0;
    // 初始化 map 包含 {0:1}，处理前缀和本身能被 k 整除的情况
    map.put(0, 1);
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        // 统一处理负数取模，确保结果为正，符合数学定义
        int r = (sum % k + k) % k;
        // 若当前前缀和模 k 的值之前出现过，说明中间这段子数组和能被 k 整除
        ret += map.getOrDefault(r, 0);
        // 更新该模值的出现次数
        map.put(r, map.getOrDefault(r, 0) + 1);
    }
    return ret;
}