poj 3370 鸽笼原理知识小结 - c++编程基础

中学就听说过抽屉原理，可惜一直没机会见识，现在这题有鸽笼原理的结论，但其实知不知道鸽笼原理都可以做

先总结一下鸽笼原理：

有n+1件或n+1件以上的物品要放到n个抽屉中，那么至少有一个抽屉里有两个或两个以上物品。

如果你知道这个结论：

a1,a2,a3...am是正整数序列，至少存在整数k和r,1<=k

证明比较简单:

Sk表示前k个数之和，

(1)若Sk%m==0,前k个数就是m的倍数

（2）如果Sn与St模m同余，那么从t+1到n这些数之和模m等于0.

即使你不知道这个结论，DP厉害的话，应该能想到用前n项的和去思考的思想

有这个结论知必有解。

贴代码之前，在总结一下鸽笼原理的结论：

推论1：m只鸽子，n个笼，则至少有一个鸽笼里有不少于[(m-1)/n]+1只鸽子。

推论2:若取n*(m-1)+1个球放进n个盒子，则至少有1个盒子有m个球。

推论3：若m1,m2,...mn是n个正整数，而且（m1+m2+...+mn）/n>r-1

则m1,m2,...mn中至少有一个数不小于r

直接贴代码吧：没啥解释的，700多MS,当时judge的时候我还害怕TLE

#include  
#include  
using namespace std;  
#define N 100002  
  
int sum[N],pos[N];  
  
int main()  
{  
  
    int c,n,i,r,t,j;  
  
    while(scanf("%d%d",&c,&n),c+n)  
    {  
        memset(pos,-1,sizeof(pos));  
        bool flag=false;  
  
        scanf("%d",&sum[0]);  
        sum[0]%=c;  
        pos[sum[0]]=0;  
        if(sum[0]==0){printf("1\n");flag=1;}  
  
        for(i=1;i