poj 3370 鴿籠原理知識小結

中學就聽說過抽屜原理，可惜一直沒機會見識，現在這題有鴿籠原理的結論，但其實知不知道鴿籠原理都可以做   先總結一下鴿籠原理：     有n+1件或n+1件以上的物品要放到n個抽屜中，那麼至少有一個抽屜裡有兩個或兩個以上物品。   如果你知道這個結論： a1,a2,a3...am是正整數序列，至少存在整數k和r,1<=k<r<=m,使得ak+a(k+1)+...+a(r)是m的倍數。   證明比較簡單:   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<cstdio>  
#include<cstring>  
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<n;i++)  
        {  
            scanf("%d",&sum[i]);  
            if(flag)continue;  
            sum[i]%=c;  
            sum[i]+=sum[i-1];  
            sum[i]%=c;  
            if(sum[i]==0)  
            {  
                for(j=0;j<i;j++)  
                    printf("%d ",j+1);  
                printf("%d\n",i+1);  
                flag=1;  
                continue;  
            }  
            if(pos[sum[i]]==-1)pos[sum[i]]=i;  
            else  
            {  
                for(j=pos[sum[i]]+1;j<=i;j++)  
                    if(j!=i)printf("%d ",j+1);  
                    else printf("%d\n",i+1);  
                flag=1;  
            }  
        }  
          
    }  
  
    return 0;  
}