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整除。
1/*************************************************************************
2 > File Name: code/poj/2356.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年08月21日 星期五 13时43分41秒
6 ************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#define y0 abc111qqz
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define tm crazy111qqz
25#define lr dying111qqz
26using namespace std;
27#define REP(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef unsigned long long ULL;
30const int inf = 0x3f3f3f3f;
31const int N=2E4+7;
32int a[N];
33int sum[N];
34int n;
35int p[N];
36int main()
37{
38 scanf("%d",&n);
39 sum[0]= 0;
40 for ( int i = 1 ; i <= n ; i++){
41 scanf("%d",&a[i]);
42 sum[i] = (sum[i-1] + a[i])%n;
43 }
44 memset(p,0,sizeof(p));
45 for ( int i = 1 ; i <= n ; i++){
46 if (sum[i]==0){
47 printf("%d\n",i);
48 for ( int j = 1 ; j <= i ; j++){
49 printf("%d\n",j);
50 }
51 break;
52 }
53 if (p[sum[i]]){
54 // cout<<"111qqz"<<endl;
55 printf("%d\n",i-p[sum[i]]);
56 for ( int j = p[sum[i]]+1 ; j <= i ; j++){
57 printf("%d\n",j);
58 }
59 break;
60 }
61 p[sum[i]] = i;
62
63 }
64
65 return 0;
66}