暴力前缀和求解o(n^2)

long res = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++) 
        if ((s[i] - s[j - 1]) % k == 0) res++;

对于内层循环，寻找i之前(包括i)的j满足条件的个数
记r = i, l = j - 1, 则l的范围就是0 ~ r - 1
满足条件s[i] - s[j - 1]) % k == 0变为s[r] - s[l]) % k == 0
再变s[r] % k == s[l] % k：即找r左边的%k相等的数量(l属于0 ~ r - 1)

记数组cnt[i]表示余数为i的数量
枚举r的时候动态维护cnt数组
cnt[0] = 1，简单来说就是考虑ai自己就是k倍区间，详见： https://www.acwing.com/solution/content/91503/

import java.util.*;

public class Main {
    static final int N = 100010;
    static int[] cnt = new int[N];
    static long[] s = new long[N];
    static int n, k;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();

        for (int i = 1; i <= n; i++) s[i] = s[i - 1] + sc.nextInt();

        long res = 0;
        cnt[0] = 1;//cnt[s[0] % k] ++;//左端点在0有意义
        for (int i = 1; i <= n; i++) {
            /*当s[i] % k == 
            0时需要多加一个1，但是cnt[0]初始化为1就不需要了
            */
            res += cnt[(int) (s[i] % k)];//加上r左边%k相等的数
            cnt[(int) (s[i] % k)]++;//当前余数多一个
        }
        /* <==>
        long res = 0;
        for (int i = 0; i <= n; i++) {
            res += cnt[(int) (s[i] % k)];
            cnt[(int) (s[i] % k)]++;
        }
        */
        System.out.println(res);
    }
}