POJ2356 Find a multiple 抽屉原理（鸽巢原理） - c++编程基础

题意：给你N个数，从中取出任意个数的数使得他们的和是 N的倍数；

在鸽巢原理的介绍里面，有例题介绍：设a1,a2,a3,……am是正整数的序列，试证明至少存在正数k和l，1<=k<=l<=m,是的和ak+ak+1+……+al是m的倍数，接下来开始证明：

构造一个序列s1=a1,s2=a1+a2，……，sm=a1+a2+……+am,那么会产生两种可能：

1：若有一个sn是m的倍数，那么定理成立：

2：假设上述的序列中没有任何一个元素是m的倍数，令rh ≡ sh mod m;其中h=1,2,……,m;我们已知上面的所有项都非m的倍数，得到s1模m的余数是r1,s2模m的余数是r2,同理往下类推，r是一个余数序列，在这里所有的余数都不为0，因为假设是不存在有m的倍数的，所以r序列的元素小于m，根据抽屉原理（鸽巢原理），m个余数在[1,m-]区间里的取值至少存在一对rh,rl，并且满足 rh=rk,即sh和sk满足

sk ≡ sh mod m，那么假设h>k，得到

sh-sk = (a1+a2+……+ah) - (a1+a2+……+ak)

sh - sk =ak+1 +ak+2 +……+ah ≡ 0 mod m（此处的k是序列a的下标）

证明到此结束；

那么熟悉根据抽屉原理（鸽巢原理），稍微动动脑筋便能做这道题目了

先处理出前k个数的sum[k] (1 <= k <= n) 同时对n进行取余操作，如果有一个sum[k]等于0，那么这个sum就是n的倍数，然后根据鸽巢原理，有n个余数r ,0 <= r <=n ,如果没有余数0，那么至少有两个余数是相同的，即这两个sum相减得到的差就是n的倍数，

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-7 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; // int a[100012],mark[1000012],sum[100012]; void clear() { memset(a,0,sizeof(a)); memset(sum,0,sizeof(sum)); memset(mark,0,sizeof(mark)); } int main() { int n; while(scanf("%d",&n)==1) { clear(); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum[i] = sum[i-1] + a[i]; sum[i] %= n; mark[i] = 0; } for(int i=1;i<=n;i++) { if(sum[i]==0) { printf("%d\n",i); for(int j=1;j<=i;j++) { printf("%d\n",a[j]); } break; } else if(mark[sum[i]]) { printf("%d\n",i-mark[sum[i]]); for(int j=mark[sum[i]]+1;j<=i;j++) printf("%d\n",a[j]); break; } mark[sum[i]]=i; } } return EXIT_SUCCESS; }