k倍区间
时间限制：2.0s 内存限制：256.0MB
问题描述
给定一个长度为N的数列，A1, A2, ... AN，如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数，我们就称这个区间[i, j]是K倍区间。
你能求出数列中总共有多少个K倍区间吗？
输入格式
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)
输出格式
输出一个整数，代表K倍区间的数目。
样例输入
5 2
1
2
3
4
5
样例输出
6
数据规模和约定
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 2000ms
解题思路 这个题最主要用的是动态规划，通过把所有的输入值累加，并且取模，通过计算每个模值的次数来看有多少需要的解。
比如 3 4 5 6 7与 k=3 模为1 ，3 4 5 6 7 8 9 10与k=3 模为 1，两个模相同的序列 相减所得 序列 8 9 10 符合要求。其余同理，所以我们可以得出用模的次数可以表示其结果。
不过这种模的结果只是表示其区间的结果，还有单个取模为0的值，如 3 4 5 k=3 模为0 ，3 k=3模为零，按上面来算 就是 4 5 序列 为结果 少了 加上3 的结果 还有包括3 自己本身的结果，所以我们需要在结果上在加上一遍模为0次数的值。
同时还要注意结果的范围长度，在蓝桥练习系统中，sum用int类型 会有一个错误，用long 就没有问题。
1 import java.util.Scanner;
2
3 public class Main {
4 public static void main(String arg[]){
5 Scanner in=
new Scanner(System.in);
6 int n=
in.nextInt();
7 int m=
in.nextInt();
8 int sz[]=
new int[n+1];
//装载每个输入的值相加后的和
9 int sz1[]=
new int[m+1];
//装载每个余数出现次数
10 long sum=0
;
11 for (
int i = 1; i <= n; i++
) {
12 sz[i]=(in.nextInt()+sz[i-1])%
m;
13 sum+=
sz1[sz[i]];
14 sz1[sz[i]]++
;
15 }
16 System.out.println(sum+sz1[0
]);
17
18 }
19 }
转载于:https://www.cnblogs.com/hwhWorld/p/10492339.html
相关资源：JAVA上百实例源码以及开源项目
