蓝桥杯 Java k倍区间

 前缀和的一个神奇算法，这道题暴力是遍历前缀和的差，也就是遍历所有区间和看他是不是能不能正好除尽k

这道题的技巧是将所有前缀和和k求余
按照求余的结果放在一个数组中
那么余数为0的前缀和a一定满足要求（[0,a]）
余数相同的两两组合范围相减也符合要求，所以有Cn2即 (v[i]*(v[i]-1))/2个

那么就把复杂度为O(n2)的循环遍历前缀和算法降低为复杂度为O(n)的算前缀和余数分类的算法。值得学习。

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
 
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int k = scan.nextInt();
        long[] q = new long[n+1];
        long[] v = new long[k];
        for(int i = 1;i <= n;i++){
          q[i] = scan.nextInt() + q[i-1];
          v[(int)(q[i]%k)]++;
        }
        long ans = 0;
        ans += v[0];
        for(int i = 0;i < k;i++){
          ans += (v[i]*(v[i]-1))/2;
        }
 
        System.out.println(ans);
        //在此输入您的代码...
        scan.close();
    }
}