题目描述
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 a 1 , … , a n (1 ≤ a i ≤ 100000 ), where a i 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 a i 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.
Sample Input
4 5
1 2 3 7 5
3 6
7 11 2 5 13 17
0 0
Sample Output
3 5
2 3 4
题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1808
解题思路
这道题运用的就是抽屉原理中的整除问题，以下是相关定理的运用（百度文库：抽屉原理的典型问题）：
把所有整数按照除以某个自然数m的余数分为m类，叫做m的剩余类或同余类，用[0]，[1]， [2]，…，[m-1]表示.每一个类含有无穷多个数，例如[1]中含有1，m+1，2m+1，3m+1，…。在研究与整除有关的问题时，常用剩余类作为抽屉.根据抽屉原理，可以证明：任意n+1个自然数中，总有两个自然数的差是n的倍数。
因此，我们每输入一个数，可以记录一个到目前为止的和，将这些和对c进行取模，根据上面的定理，我们就可以找到两个数，这两个数的差为c的倍数。同时，这两个的数的差可以等价于这两个数之间所有的数的和，这样我们就能记录这两个数的下标，输出这两个数中间所有的下标即可。
AC代码
639M/3372K/G++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
typedef long long ll;
int a[100005];
ll sum[100005], index[100005];
int main()
{
int c, n;
while (~scanf("%d%d", &c, &n) && c + n)
{
memset(sum, 0, sizeof(sum));
memset(index, 0, sizeof(index));
for (int i = 1; i <= n; i++)
{
scanf("%d", a + i);
sum[i] = (sum[i - 1] + a[i]) % c;
}
int left, right;
for (int i = 1; i <= n; i++)
{
if (sum[i] == 0)
{
left = 1;
right = i;
break;
}
else if (index[sum[i]])
{
left = index[sum[i]] + 1;
right = i;
break;
}
else
{
index[sum[i]] = i;
}
}
printf("%d", left);
for (int i = left + 1; i <= right; i++)
{
printf(" %d", i);
}
printf("\n");
}
return 0;
}