蓝桥杯 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();}
}