题目
给定一个长度为 N 的数列，A1,A2,…AN，如果其中一段连续的子序列 Ai,Ai+1,…Aj 之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。
你能求出数列中总共有多少个 K 倍区间吗？
输入格式
第一行包含两个整数 N 和 K。
以下 N 行每行包含一个整数 Ai。
输出格式
输出一个整数，代表 K 倍区间的数目。
数据范围
1≤N,K≤100000,
1≤Ai≤100000输入样例：
5 2 1 2 3 4 5输出样例：
6
思路
第一种O(n^3) 暴力枚举
for(int i=1;i<=n;i++){ // 从1枚举到n for(int j=1;j<=i;j++){ // 从1枚举到ifor(int k=j;k<=i;k++) // 计算i~j的和sum += a[k]if(sum%k==0) res++; }
}第二种O(n^2) 使用前缀和（仍然过不了，甚至过的点是跟暴力一样的）
前缀和（一维+二维）-CSDN博客
for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){if((s[i]-s[j-1])%k==0) res++;}
}第三种O(N) 在前缀和基础上优化
在第二种方法的第二层循环里面 ，目的是判断 ，即
，判断两个余数是否相等，如果在第
层循环里面，我们可以知道从
到
中有 哪些的前缀和
等于
，那么这一段就是K倍区间。
新开一个数组 cnt[ ] ,存储前 i 个值的余数情况。
cnt[0] = 1; // 如果某个数自身也可以整除k，说明取余为0，所以cnt[0]初始化为1,
for(int i=1;i<=n;i++){int t = s[i]%k; // i个值的前缀和对k取余res += cnt[t]; // 加上前 0~i-1 有相同的余数的个数cnt[t]++; // 第i个前缀和取余k的余数对应的cnt++
}完整代码
import java.io.*;class Main{static int N = 100010;static int n,k;static int[] cnt = new int[N];static long res;static long[] s = new long[N];public static void main(String[] args) throws IOException{BufferedReader in = new BufferedReader(new InputStreamReader(System.in));String[] str = in.readLine().split(" ");n = Integer.parseInt(str[0]);k = Integer.parseInt(str[1]);for(int i=1;i<=n;i++){ // 求前缀和s[i] = s[i-1]+Integer.parseInt(in.readLine());}cnt[0] = 1;for(int i=1;i<=n;i++){long t = s[i]%k;res += cnt[(int)t];cnt[(int)t]++;}System.out.println(res);}
}
