题目链接：
题目描述
给定一个长度为 N 的数列，A1, A2, AN，A1,A2,⋯AN，如果其中一段连续的子序列 Ai,Ai+1, Aj，Ai,Ai+1,⋯Aj ( i≤j ) 之和是 K 的倍数，我们就称这个区间 [i,j] 是 K 倍区间。
你能求出数列中总共有多少个 K 倍区间吗？
输入描述
第一行包含两个整数 N 和 K
以下 N 行每行包含一个整数 Ai
输出描述
输出一个整数，代表 K 倍区间的数目。
输入输出样例
示例
输入
5 2 1 2 3 4 5
编辑
输出
6
运行限制
- 最大运行时间：2s
- 最大运行内存: 256M
解法一：
import java.util.Scanner; public class k倍区间 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), k = sc.nextInt(); // 初始化桶 int[] bucket = new int[k]; bucket[0] = 1; long sum = 0; // 记录计数结果 int preSum = 0; // 记录前缀和取 k 的余数的结果 for (int i = 0; i < n; i++) { int num = sc.nextInt(); preSum = (preSum + num) % k; // 特判负数的情况 if (preSum < 0) { preSum += k; } sum += bucket[preSum]; bucket[preSum]++; } System.out.println(sum); sc.close(); } }
解法二：
import java.util.Scanner; public class k倍区间 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int N = scan.nextInt(); int k = scan.nextInt(); int[] sums = new int[N+1]; long[] cnt = new long[k]; sums[0] = 0; cnt[0] = 1; int t; for (int i = 1; i <= N; ++i) { t = scan.nextInt(); sums[i] = (sums[i-1] + t) % k; cnt[sums[i]]++; } long ans = 0; for (int i = 0; i < k; ++i) { ans += (cnt[i] * (cnt[i] -1)/2); } System.out.println(ans); scan.close(); } }
