思路

1. 暴力做法是枚举所有区间起点、终点，计算总和再判断是否为$K$的倍数
   • 其中计算区间元素总和，因为是一段位置连续的数字，所以可以使用前缀和简化，$\sum_{x=i}^{j}a_x = S_j-S_{i-1}$
   • 要求总和是$K$的倍数，所以对于每个新获取到的数，只需要先计算出前缀和，再向前遍历找到所有总和之差模$K$为0的个数即可（之前每个满足结果为0的前缀和都表示可组成一个新的$K$倍区间）
   • 又因为$(S_j-S_{i-1})\ mod\ K = 0 \Longrightarrow S_j\ mod\ K = S_{i-1}\ mod\ K$，所以在计算前缀和时，可以事先模$K$再保存到数组（此时前缀和实际存的是模$K$的结果，$S_j = (\sum_{x=0}^{j}a_x)\ mod\ K$），则向前遍历时只需要判定两个余数是否相等即可
2. 经过上一步的简化，需要枚举的只剩下区间终点和终点之前所有位置的前缀和，对于每个终点向前遍历前缀和的过程，很多位置的都是重复读取的（比如终点索引为3则遍历范围为0~2，终点索引为5则遍历范围为0~4），可以引入哈希表或数组，统计此前某个余数出现的次数，从而省去前缀和的遍历
3. 注意要考虑“某个数本身就是$K$的倍数，可自成一个区间”的情况，一种办法是前缀和模$K$余数为0时统计值直接+1，另一种是初始时余数为0的情况有1种

代码

import java.util.*;
import java.lang.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n, k;
    static int[] cnt = new int[100010];

    public static void main(String[] args) {
        n = scanner.nextInt();
        k = scanner.nextInt();
        int s = 0;  // 前缀和初始为0
        cnt[s]++;  // 和为0的区间初始有1种 （什么都不选）
        long res = 0;  // 记录总数 爆int
        for (int i = 1; i <= n; i++) {
            s += scanner.nextInt();  // 前缀和更新
            s %= k;  // 取模
            // 以下所提的区间 都是以 输入数据的首元素 为区间起点
            res += cnt[s];  // 查找之前总和为s的区间总数  其中每个区间都能与最新获取的数组成一个新的k倍区间
            cnt[s]++;  // 总和为s的区间总数+1 开始记录下一个数
        }
        System.out.println(res);
    }
}