你好呀，我是灰小猿，一个超会写bug的程序猿！

欢迎大家关注我的专栏“每日蓝桥”，该专栏的主要作用是和大家分享近几年蓝桥杯省赛及决赛等真题，解析其中存在的算法思想、数据结构等内容，帮助大家学习到更多的知识和技术！

标题：K倍区间

给定一个长度为 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

【资源约定】

峰值内存消耗(含虚拟机) < 256M

CPU消耗< 1000ms

请严格按要求输出，不要画蛇添足地打印类似: " 请您输人..”的多余内容.

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码.

不要使用package语句。不要使用jdk1.7及以上版本的特性.

主类的名字必须是: Main, 否则按无效代码处理.

提交程序时，注意选择所期望的语言类型和编译器类型.

解题思路：

对于本题在求解的时候可能最先想到的是使用暴力枚举的方法，将每一个区间都列出来进行判断，但是这样的方法虽然可行，但是只针对于小量的数据，对于像题中所给的范围来说，就已经远远的超出了运行时间，所以我们应该想办法在原来暴力枚举代码的基础上对代码进行优化。

所采用的方法就是前缀和的方式，我们可以在输入数据的时候就求出每输入一个数据得到的数据的总和，并且把该总数记录下来，之后我们可以判断总数与K的余数是否为0。如果是，则说明该从第一个数到该数的总数和是k的倍数；同时如果余数不是0，那么我们其实也可以推出来余数相同的两个区间之间的差也一定是K的倍数。这句话要注意理解。利用这一特性，我们就可以求出符合要求的区间数。

答案源码：

package 一七年省赛真题;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Year2017_Bt10 {

	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int K = scanner.nextInt();
		int [] arr = new int[N+1];
		int [] sumArr = new int[N+1];
		sumArr[0] = 0;
		int ans=0;
		Map<Integer, Integer> maps = new HashMap<Integer, Integer>();
		maps.put(0, 1);
		for (int i = 1; i <= N; i++) {
			arr[i] = scanner.nextInt();//将输入的数据存放到数组中
			sumArr[i] = (arr[i] + sumArr[i-1])%K;	//计算前i个数的和与K的mod
			//判断前i个数的和与k的余是否存储在map中
			if (maps.get(sumArr[i])==null) {
				maps.put(sumArr[i],1);
			}else {
				maps.put(sumArr[i], maps.get(sumArr[i])+1);
			}							
		}
		for (int i = 0; i <= K-1; i++) {
			if (maps.get(i)!=null) {
//				System.out.println(i + " " + maps.get(i));
				ans+=maps.get(i)*(maps.get(i)-1)/2;
			}
		}

		System.out.println(ans);
	}	

}

输出样例：

其中有不足或者改进的地方，还希望小伙伴留言提出，一起学习！

感兴趣的小伙伴可以关注专栏！

灰小猿陪你一起进步！