poj 2356 Find a multiple【鸽巢原理 模板应用】

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#define N 10000+100

using namespace std;

int a[N];
int sum[N];
int yu[N];

struct node
{
	bool k;
	int pos;

}q[N];


int main()
{
	int n;
	int i, j;
	int left, right;

	while(~scanf("%d", &n))
	{
		bool flag1=false;
        bool flag2=false;

		for(i=0; i<n; i++){
			scanf("%d", &a[i] );
			if(i==0) sum[i]=a[i];
			else sum[i]=sum[i-1]+a[i];
		}
		left=0;
		memset(q, 0, sizeof(q));

		for(i=0; i<n; i++){
			yu[i]=sum[i]%n;
			if(yu[i]==0){
				flag1=true; right=i; break;
			}
			else{
				if(q[yu[i]].k ){
					flag2=true;
					left=q[yu[i]].pos; right=i; break;
				}else{
					q[yu[i]].k=true; q[yu[i]].pos=i;
				}
			}
		}
		if(flag1){
			printf("%d\n", right+1 );
			for(i=0; i<=right; i++){
				printf("%d\n", a[i] );
			}
		}
		else if(flag2){
            printf("%d\n", right-left );
            for(i=left+1; i<=right; i++){
				printf("%d\n", a[i] );
			}
		}
	}
	return 0;
}