蓝桥杯2017年第八届真题-k倍区间 （Java代码）

解题思路:气死我了，写道一半，突然没网了，然后写的东西全不见了，生气！

               这道题，暴力不可以，所以需要想办法。用数学思维来想一想

                1，2，3，4，5      如果叫你求其中任何一个区间，你可能会选择一个一个的去数，然后相加，这也是我们暴力求解的做法，但是数据多了呢？如果让你去算，你怎么办？比如我给你一个下标[2，30]，叫你求这个区间内的和，你怎么求呢？

                哇，不会呢！

                傻眼，我们肯定是用前30项的和减去前1项的和呀，为什么是前一项不是前2项？因为这里的2，是个开区间，我们要取得.来来来，用我们的语言来表示他，是不是sum=sum[j]-sum[i-1]，这里的i和j分别是区间两端的点。

                好了，然后题目要求我们算的是，K倍的sum，也就是sum%k==0的情况，再来，sum等于什么？

于是乎，有：sum[j]%k==sum[i-1]%k，这时候我们只要算出，sum[j]和sum[i-1]的情况有多少，是不是就算出答案了呢，来，我们试试看。

            1，2，3，4，5            k=2

            sum[1]=1       %2过后是     1        dp[sum[1]%k]++

            sum[2]=3       %2过后是     1           哇，这个1和前面的1，重复了。对的，这时候我们就要计数了。

             count++;       count+=dp[sum[2]%k]++

            sum[3]=6     %2过后是       0          dp[sum[3]%k]++

            sum[4]=10   %2过后是       0           前面的0，重复了，此时我们再一次计数

            count++        count+=dp[sum[4]%2]++

            sum[5]=15    %2过后是     1            前面的1，重复了2此，我们加两次

            count+2;        

问题是，怎么用代码实现上述过程？不妨建造一个dp[1]大小的数组，用来存放0和1的个数

我现在用红色的字体，写在上面。看到了吗，算一算，count=4。

？？？？等于4，错的啊，答案等于6啊。的确，因为我们忽略了当区间本身是K的倍数的情况，你看嘛，我们计数的条件是判定有两个相等的区间和，所以区间本身为K的倍数是没有被我们考虑进来的。然后程序就清晰了！

注意事项:

参考代码:

import java.util.Scanner;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		int k=in.nextInt();
		int arr[]=new int[n+1];
		for(int i=1;i<=n;i++)arr[i]=in.nextInt();
		long count=0;
		int sum[]=new int[n+1];
		int dp[]=new int [n+1];
		dp[0]=0;//表示第一个数前缀和是多少
		for(int i=1;i<=n;i++){
			sum[i]=(sum[i-1]+arr[i])%k;//存放前缀和并取模的表
			count+=dp[sum[i]];//这句代码要好好理解，dp[sum[i]]是什么意思呢？
			dp[sum[i]]++;     //sum[i]代表前面取模是0或者1，而dp[sum[i]表示前面出现的0的个数和1的个数，出现第一次，我们是不会记录的
			
		}
		
		
			
		System.out.println(count+dp[0]);
		
	}

}