学步园

poj 2356  http://poj.org/problem?id=2356

import java.util.Scanner;
public class Main {
	//抽屉原理（鸽巢原理）最基础的原理便是n+1的物体放到n个盒子里，至少有一个盒子放了两个物体
	//有n个数，从中选出几个数的和是n的倍数。
    //结论是任意的n个数，必然能找到连续的m个数之和是n的倍数。
    //组合数学书中，黑书都有介绍。Sk表示a1+a2+……ak,如果Sk是n的倍数，那就直接取Sk了，否则S1-Sn除n的余数分布在1---（n-1）这n-1个数中，运用鸽巢原理，必然有两个的余数相同，即(Si%n)=(Sj%n),即(Sj-Si)%n=0，证毕
	static int record[];
	static void print(int start,int end)
	{
		System.out.println(end-start+1);
		for(int i=start;i<=end;i++)
		{
			System.out.println(record[i]);
		}
	}
	public static void main(String[] args) {
	 Scanner scanner=new Scanner(System.in);
	 while(scanner.hasNext())
	 {
		 int n=scanner.nextInt();
		 record=new int[n+1];
		 int sum[]=new int[n+1];
		 int flag[]=new int[n+1];
		 for(int i=1;i<=n;i++)
		 {
			 record[i]=scanner.nextInt();
			 sum[i]=(sum[i-1]+record[i])%n;
		 }
		 for(int i=1;i<=n;i++)
		 {
			 if(sum[i]==0)
			 {
				 print(1, i);
				 break;
			 }
			 else if(flag[sum[i]]!=0){
				print(flag[sum[i]]+1, i);
				break;
			}
			 else {
				flag[sum[i]]=i;
			}
		 }
	 }
	}
}

poj  3370   http://poj.org/problem?id=3370   开挂可过

import java.io.BufferedInputStream;
import java.io.IOException;
public class Main {
	//抽屉原理（鸽巢原理）最基础的原理便是n+1的物体放到n个盒子里，至少有一个盒子放了两个物体
	//有n个数，从中选出几个数的和是n的倍数。
    //结论是任意的n个数，必然能找到连续的m个数之和是n的倍数。
    //组合数学书中，黑书都有介绍。Sk表示a1+a2+……ak,如果Sk是n的倍数，那就直接取Sk了，否则S1-Sn除n的余数分布在1---（n-1）这n-1个数中，运用鸽巢原理，必然有两个的余数相同，即(Si%n)=(Sj%n),即(Sj-Si)%n=0，证毕
	
	public static BufferedInputStream bis = new BufferedInputStream(System.in);
	public static int read() throws IOException {
		int i;
		while ((i = bis.read()) < 48)
			if (i == -1)
				return -1;
		int temp = 0;
		while (i > 47) {
			temp = temp * 10 + i - 48;
			i = bis.read();
		}
		return temp;
	}
	static void print(int start,int end)
	{
		for(int i=start;i<end;i++)
		{
			System.out.print(i+" ");
		}
		System.out.println(end);
	}
	public static void main(String[] args) throws IOException {
	 while(true)
	 {
		 int m=read();int n=read();
		 if(n==0&&m==0)break;
		 int record[]=new int[n+1];
	     int sum[]=new int[n+1];
	     int flag[]=new int[n+1];
		 for(int i=1;i<=n;i++)
		 {
			 record[i]=read();
			 
		 }
		 for(int i=1;i<=n;i++)
		 {
			 sum[i]=(sum[i-1]+record[i])%m;
			 if(sum[i]==0)
			 {
				 print(1, i);
				 break;
			 }
			if(flag[sum[i]]!=0){
				print(flag[sum[i]]+1, i);
				break;
			}
			flag[sum[i]]=i;
		 }
	 }
	}
}