POJ 3370 Halloween treats - 鴿巢原理

POJ 3370 Halloween treats - 鴿巢原理

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₁ , ... , 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

鴿巢原理也叫抽屜原理；

【抽屜原理】：原理1 把多於n個的物體放到n個抽屜裡，則至少有一個抽屜裡的東西不少於兩件；

原理2 把多於mn(m乘以n)個的物體放到n個抽屜裡，則至少有一個抽屜裡有不少於m+1的物體。

原理3 把無窮多件物體放入n個抽屜，則至少有一個抽屜裡 有無窮個物體。.

原理 4 把（mn－1）個物體放入n個抽屜中，其中必有一個抽屜中至多有（m—1）個物體。

引用：http://blog.csdn.net/new_wu/article/details/7367025

思路：定理：

設a1、a2……am是正整數的序列，則至少存在整數k和l，（1<=k

證明：x%m的余數有（m-1）中可能，即設有（m-1)個鴿巢，設sn代表（a1+a2+...+an）則m個sn產生m個余數，根據鴿巢原理，一定至少有兩個s的余數相等，將這連個s想減，中間a(k+1) + a(k+2) + ... ... +al一定是m的倍數。

引用：http://blog.csdn.net/LiWen_7/article/details/8047273

偷懶了，上面引用一下別人博客的東西。

最好的抽屜原理解說，當然是書本：Discrete Mathematics and its Application

根據定理，也就說本題不可能出現沒有答案的情況，其中的關鍵是要求了c <= n，如果沒有這個條件，那麼本題就無法應用抽屜原理了。

#include 
#include 
#include 

const int MAX_N = 100001;
int arr[MAX_N], modMap[MAX_N];

int main()
{
	int c, n;
	arr[0] = modMap[0] = 0;
	while (scanf("%d %d", &c, &n) != EOF && c)
	{
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", arr+i);
			modMap[i] = -1;
		}
		int lastMod = 0, curMod = 0, l = -1, r = -1;
		for (int i = 1; i <= n; i++)
		{
			curMod = (arr[i] + lastMod) % c;
			if (modMap[curMod] != -1)
			{
				l = modMap[curMod] + 1;
				r = i;
				break;
			}
			modMap[curMod] = i;
			lastMod = curMod;
		}
		if (-1 != l)
		{
			while (l <= r) printf("%d ", l++);
			putchar('\n');
		}
		else puts("no sweets");//可以去掉，因為根據題意，必定有解
	}
	return 0;
}