題意:有n個數,求是否存在一些數的和是n的倍數。若存在,輸出即可。不存在,輸出0.
思路:鴿巢原理的題目,組合數學課本上的原題。可以把和求出來,然後對n取余,因為有n個和,對n取余,如果余數中沒有出現0,根據鴿巢原理,一定有兩個數的余數相同,兩個和想減就是n的倍數。如果余數出現0,自然就是n的倍數。也就是說,n個數中一定存在一些數的和是n的倍數。求余輸出即可。
代碼:
[cpp]
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
const int N = 10010;
int num[N],sum[N],pos[N];
bool flag[N];
int main(){
//freopen("1.txt","r",stdin);
int n;
while(scanf("%d",&n) != EOF){
CLR(num,0);
CLR(sum,0);
CLR(pos,-1);
CLR(flag,false);
for(int i = 1; i <= n; ++i){
scanf("%d",&num[i]);
sum[i] = sum[i-1] + num[i];
}
for(int i = 1;i <= n; ++i){
int x = sum[i] % n;
if(flag[x]){
int y = pos[x];
printf("%d\n",i - y);
for(int j = y+1; j <= i; ++j)
printf("%d\n",num[j]);
break;
}
if(x == 0){
printf("%d\n",i);
for(int j = 1; j <= i;++j)
printf("%d\n",num[j]);
break;
}
flag[x] = true;
pos[x] = i;
}
}
return 0;
}