題目：給定一個長度為?N?的數列，A1,A2,?AN?，如果其中一段連續的子序列?Ai,Ai+1,?Aj(?i≤j ) 之和是?K?的倍數，我們就稱這個區間[i,j]?是 K 倍區間。

你能求出數列中總共有多少個?K 倍區間嗎？

輸入描述

第一行包含兩個整數?N?和?K(?1≤N,K≤105 )。

以下 N 行每行包含一個整數?AiAi??(?1≤Ai≤105 )

輸出描述

輸出一個整數，代表 K 倍區間的數目。

輸入輸出樣例

示例

輸入

5 2
1
2
3
4
5

輸出

6

解題思路+代碼：(引用題解區 作者：風之理

解題思路

①前綴和：是每一個都是前面累加的（第一個是0+第一個） ②前綴和%K==》可以找到K=0，它一定是K的倍數 ③理解一個東西：任意兩個前綴和的差值就是一個區間 ④而前綴和的差值為0，也一定是K的倍數 ⑤（3，3，3，3）---》任意兩個組合：（n*(n-1)/2))

代碼：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);long N= sc.nextInt();long K= sc.nextInt();long sum=0;long [] n1=new long[100010];long [] n2=new  long[(int) K];for (int i = 0; i < N; i++) {long s= sc.nextInt();n1[i+1]=n1[i]+s;n2[(int)(n1[i+1]%K)]++;}sum +=n2[0];for (int i = 0; i < K; i++) {sum+=(n2[i]-1)*n2[i]/2;}System.out.println(sum);sc.close();}}

?個人想了這題很久，但是提交代碼只能通過兩個用例：

總結： 個人認為這題還是有點難，ai之后發現高效的解法需要用到前綴和與哈希表來計算，大家也可參考大佬的解題思路~