?前綴和的一個神奇算法，這道題暴力是遍歷前綴和的差，也就是遍歷所有區(qū)間和看他是不是能不能正好除盡k

這道題的技巧是將所有前綴和和k求余
按照求余的結(jié)果放在一個數(shù)組中
那么余數(shù)為0的前綴和a一定滿足要求（[0,a]）
余數(shù)相同的兩兩組合范圍相減也符合要求，所以有Cn2即?(v[i]*(v[i]-1))/2個

那么就把復(fù)雜度為O(n2)的循環(huán)遍歷前綴和算法降低為復(fù)雜度為O(n)的算前綴和余數(shù)分類的算法。值得學(xué)習(xí)。

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