看pigeon hole原理也看过好多遍了，但是一直没有使用过。

一开始看到这道题，还真被难倒了，怎么使用pigeon hole呢？

可以说pigeon hole是最简单不过的原理了，基本上是常识，但是既然总结为一条数学原理，那么就肯定是有原因的，正如这道题一样，感觉简单，但是确实需要很好的数学思维的。

引用一下这个博客的原文：http://hi.baidu.com/xiao_yu_feng/item/c7f83df9849e5e1ea7298869

鸽笼原理的简单应用（pku2356 3370）

定理：给定m个数a1,a2,...,an.则比存在整数k和l（0<=k

a1,a1+a2,...,a1+a2+..+an.

若上面n个数中有能被n整除的。那么显然存在连续个的数之和能被n整除,从1--i

否则，对每一个数对n模运算。得到n个数，但是我们知道余数只能是1-->n-1,所以由鸟笼原理知道，至少有两个数的余数相同。且设为k，l（k

a1+a2+a3+....+ak与a1+a2+a3+..+al对n取模运算有相同的余数t，

a1+a2+a3+....+ak=x*n+t;

a1+a2+a3+..+al=y*n+t; 相减得a[k+1]+a[k+2]+....+a[l]=(y-x)*n,即能被n整除。

例子：n=5，分别为1，2，3，4，1

1，1+2，1+2+3，1+2+3+4，1+2+3+4+1

1，3，6，10，11

取模后，1，3，1，0，1

先判断有无取模后为0的情况，有所以为1，2，3，4

若无，取模相等的即课

第一次应用pigeon hole， 0Ms过了。

#include 
  
   
#include 
   
     #include 
    
      using namespace std; int main() { int N; scanf("%d", &N); int *arr = (int *) malloc(sizeof(int) * N); int *sumMod = (int *) malloc(sizeof(int) * N); int *iiMap = (int *) malloc(sizeof(int) * N); fill(iiMap, iiMap + N, -1); int L = -1, R = -1; int i = 0; for ( ; i < N; i++) { scanf("%d", &arr[i]); if (0 == i) sumMod[i] = arr[i] % N; else sumMod[i] = (sumMod[i-1] + arr[i]) % N; if (sumMod[i] == 0) { L = 0, R = i; break; } if (iiMap[sumMod[i]] != -1) { L = iiMap[sumMod[i]] + 1, R = i; break; } iiMap[sumMod[i]] = i; } if (-1 != R) { printf("%d\n", R-L+1); for (int i = L; i <= R; i++) { printf("%d\n", arr[i]); } } else puts("0"); free(arr), free(sumMod), free(iiMap); return 0; }