poj 2356 Find a multiple (剩余类，抽屉原理)
http://poj.org/problem?id=2356
题意：有n个数，从中选取若干个（1..n），和能被n整除。问是否有解，无解输出0，有解的话，输出个数以及选择的ai
由抽屉原理可知一定有解： 做一个带模的前缀和 sum[i]=(sum[i-1]+a[i])%n n个数，sum[i]最多有n种。 如果某个sum[i]为0，那么表示从1到i的和能被n整除。 如果所有的sum[i]不为0，那么一共有n个sum[i]，n-1个值（1..n-1），一定有sum[i]==sumj 那么a[i]到a[j]的和一定能被n整除。
/*************************************************************************
> File Name: code/poj/2356.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年08月21日 星期五 13时43分41秒
************************************************************************/
1#include<iostream>
2#include<iomanip>
3#include<cstdio>
4#include<algorithm>
5#include<cmath>
6#include<cstring>
7#include<string>
8#include<map>
9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#define y0 abc111qqz
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define tm crazy111qqz
18#define lr dying111qqz
19using namespace std;
20#define REP(i, n) for (int i=0;i<int(n);++i)
21typedef long long LL;
22typedef unsigned long long ULL;
23const int inf = 0x3f3f3f3f;
24const int N=2E4+7;
25int a[N];
26int sum[N];
27int n;
28int p[N];
29int main()
30{
31 scanf("%d",&n);
32 sum[0]= 0;
33 for ( int i = 1 ; i <= n ; i++){
34 scanf("%d",&a[i]);
35 sum[i] = (sum[i-1] + a[i])%n;
36 }
37 memset(p,0,sizeof(p));
38 for ( int i = 1 ; i <= n ; i++){
39 if (sum[i]==0){
40 printf("%d\n",i);
41 for ( int j = 1 ; j <= i ; j++){
42 printf("%d\n",j);
43 }
44 break;
45 }
46 if (p[sum[i]]){
47 // cout<<"111qqz"<<endl;
48 printf("%d\n",i-p[sum[i]]);
49 for ( int j = p[sum[i]]+1 ; j <= i ; j++){
50 printf("%d\n",j);
51 }
52 break;
53 }
54 p[sum[i]] = i;
}
return 0;
}