题意: 已知有n户人,每户会给小孩们一定数量的糖果(会给的数量假设小孩都已知),求小孩挑选哪几户人家,所得糖果总数能够使每个小孩得到相同数量的糖果,即是小孩数目的倍数?
思路:定理:
设a1、a2……am是正整数的序列,则至少存在整数k和l,(1<=k<l<=m),使得和a(k+1) + a(k+2) + ... ... +al是m的倍数。
证明:x%m的余数有(m-1)中可能,即设有(m-1)个鸽巢,设sn代表(a1+a2+...+an)则m个sn产生m个余数,根据鸽巢原理,一定至少有两个s的余数相等,将这连个s想减,中间a(k+1) + a(k+2) + ... ... +al一定是m的倍数。
代码:
#include<iostream> #include<string.h> #include<algorithm> #define N 100010 using namespace std; struct Sum { int r , h; }; Sum R[N]; bool cmp(Sum a , Sum b) { if(a.r==b.r) return a.h<b.h; return a.r<b.r; } int main() { int c , n , tmp; __int64 sum ; int flag ,b; while(scanf("%d%d",&c,&n)!=EOF && ( n+c )) { sum=0; //cout<<"c= "<<c<<" n= "<<n<<endl; flag=-1; for(int i=1;i<=n;i++) { scanf("%d",&tmp); sum+=tmp; //cout<<"sum = "<<sum<<endl; R[i].r=sum%c; // cout<<"R["<<i-1<<"].r= "<<R[i-1].r<<endl; R[i].h=i; if(R[i].r==0 ) flag=i; } // cout<<"flag= "<<flag<<endl; if(flag==-1) { sort(R+1,R+1+n,cmp); // for(int i=1;i<=n;i++) cout<<R[i].r<<" * ";cout<<endl; // for(int i=1;i<=n;i++) cout<<R[i].h<<" & ";cout<<endl; for(int i=1;i<n;i++) { if( R[i].r==R[i+1].r) {flag=R[i].h; b=R[i+1].h;} } // cout<<"a= "<<flag<<" b= "<<b<<endl; if(flag==-1) printf("no sweets\n"); else { for(int j=flag+1;j<b;j++) printf("%d ",j); printf("%d\n",b); } } else { for(int i=1;i<flag;i++) printf("%d ",i); printf("%d\n",flag); } } return 0; }