## 抽屉原理简述：

### 第一抽屉原理：

1. 把多于n+k个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。
2. 把多于mn(m乘以n)+1（n不为0）个的物体放到n个抽屉里，则至少有一个抽屉里有不少于（m+1）的物体。
3. 把无穷多件物体放入n个抽屉，则至少有一个抽屉里 有无穷个物体。

### 第二抽屉原理：

1. $（mn－1）$个物体放入n个抽屉中，其中必有一个抽屉中至多有$（m—1）$个物体 (例如，将3×5-1=14个物体放入5个抽屉中，则必定有一个抽屉中的物体数少于等于3-1=2)。

## HDU_1205 吃糖果

### Problem Description

HOHO，终于从Speakless手上赢走了所有的糖果，是Gardon吃糖果时有个特殊的癖好，就是不喜欢将一样的糖果放在一起吃，喜欢先吃一种，下一次吃另一种，这样；可是Gardon不知道是否存在一种吃糖果的顺序使得他能把所有糖果都吃完？请你写个程序帮忙计算一下。

2
3
4 1 1
5
5 4 3 2 1

No
Yes

### 代码：

#include <stdio.h>
int main()
{
__int64  n,m,t,max,sum;
scanf("%I64d",&t);
while(t--){
sum=0;
max=0;
scanf("%I64d",&n);
for(int i=0;i<n;i++){
scanf("%I64d",&m);
sum+=m;
if(max<m)
max=m;
}
sum-=max;
if(max>sum+1)
printf("No\n");
else
printf("Yes\n");
}
return 0;
}


# HDU_1808 Halloween treats

### Problem Description

Every year there is the same problem at Halloween: Each neighbour is only willing to give a certain total number of sweets on that day, no matter how many children call on him, so it may happen that a child will get nothing if it is too late. To avoid conflicts, the children have decided they will put all sweets together and then divide them evenly among themselves. From last year's experience of Halloween they know how many sweets they get from each neighbour. Since they care more about justice than about the number of sweets they get, they want to select a subset of the neighbours to visit, so that in sharing every child receives the same number of sweets. They will not be satisfied if they have any sweets left which cannot be divided.

Your job is to help the children and present a solution.

### Input

The input contains several test cases.
The first line of each test case contains two integers c and n (1 ≤ c ≤ n ≤ 100000), the number of children and the number of neighbours, respectively. The next line contains n space separated integers a1 , ... , an (1 ≤ ai ≤ 100000 ), where ai represents the number of sweets the children get if they visit neighbour i.

The last test case is followed by two zeros.

### Output

For each test case output one line with the indices of the neighbours the children should select (here, index i corresponds to neighbour i who gives a total number of ai sweets). If there is no solution where each child gets at least one sweet, print "no sweets" instead. Note that if there are several solutions where each child gets at least one sweet, you may print any of them.

4 5
1 2 3 7 5
3 6
7 11 2 5 13 17
0 0

3 5
2 3 4

### 代码：

include <cstdio>
include <cstring>

const int MAXN = 1e5+5;
int a[MAXN], SumMod[MAXN], flag[MAXN];

int main()
{
int c, n;
while(~scanf("%d%d", &c, &n) && (c+n))
{
SumMod = 0;
memset(flag, 0, sizeof(flag));
for(int i=1; i<=n; ++i)
scanf("%d", &a[i]);
for(int i=1; i<=n; ++i)
{
SumMod[i] = (SumMod[i-1] + a[i]) % c;  // 处理前缀和，并取模
if(flag[SumMod[i]] == 0)
flag[SumMod[i]] = i;
else                                   // 如果相同的余数在前面出现过
{
int j = flag[SumMod[i]] + 1;
int k = j;
for(; j<=i; ++j)                   // 公共项即为答案
if(j == k) printf("%d", j);
else printf(" %d", j);
break;
}
}
puts("");
}
return 0;
}