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