POJ 3370

题目大意是给出n和m及m个整数（n<m），要从m中找出任意个数使得其和是n的倍数，输出时就输出每一个数所在的编号

例如对于题目中的数据二，明显可以找出11，2，5，他的和是18，是3的倍数，而11，2，5对应于题目中的数据分别是2，3，4，故结果输出的是2，3，4

当然，除了2，3，4这一个解，还有1，2也是题目的解，但题目要求对于多解的情形只用输出一组解，如果无解，就输出“no sweets”但根据抽屉原理，可以得出没有无解的情况，

思路分析：运用鸽巢原理解题

首先简单说一下鸽巢原理，就是有n+1个球，放在n个盒子中，那么至少有一个盒子有两个或更多的球。

鸽巢原理理解起来并不难，但关键是将鸽巢原理运用到题目中去。

比如本题：

我们可以构造一个序列，有以下两种可能
       构造序列si，使得

          s1 = a1

          s2 = a1 + a2

          s3 = a1 + a2 + a3

          ...

          sn = a1 + a2 + ... + an

    这样，有两种可能：

       (1) 若其中有一项si是c的倍数，则即找到解；

       (2) 否则，si=ri (mod c)，取值只可能在[1,c-1]这c-1个数，然而有n个数，且c<=n，则必然存在两个数si和sj对c取模相等。首先肯定了原问题的答案肯定存在。若sj>si，则序列ai+1,...aj即为原问题的一种方案

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int Max=100005;
int a[Max];
int flag[Max];


int main()
{
	int i;
	int c,n;
	while (true)
	{
		scanf("%d%d",&c,&n);
		if (c==0&&n==0)
			break;
		memset(flag,0,sizeof(flag));
		for (i=1;i<=n;i++)
			cin>>a[i];
		int rmd=0;
		int s=1,t=1;
		for (i=1;i<=n;i++)
		{
			rmd=(rmd+a[i])%c;
			if (rmd==0)
			{
				s=1;
				t=i;
				break;
			}
			else if(flag[rmd])
			{
				s=flag[rmd]+1;
				t=i;
				break;
			}
			else
				flag[rmd]=i;
		}
		for (i=s;i<=t;i++)
		{
			printf("%d",i);
			printf("%c",i==t?'\n':' ');
		}

	}
	return 0;
}