抽屉原理（鸽巢原理）

桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。

这一现象就是我们所说的“抽屉原理”。

抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。

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

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

构造抽屉的方法

运用抽屉原理的核心是分析清楚问题中，哪个是物件，哪个是抽屉。例如，属相是有12个，那么任意37个人中，至少有一个属相是不少于4个人。这时将属相看成12个抽屉，则一个抽屉中有 37/12，即3余1，余数不考虑，而向上考虑取整数，所以这里是3+1=4个人，但这里需要注意的是，前面的余数1和这里加上的1是不一样的。

因此，在问题中，较多的一方就是物件，较少的一方就是抽屉，比如上述问题中的属相12个，就是对应抽屉，37个人就是对应物件，因为37相对12多。

抽屉问题试题链接：（我W了好几发，就是因为没有设long long,设的是int)
https://vjudge.net/contest/375775#problem/B

代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
using namespace std;
long long a[200005];
long long u[200005];
int main()
{
    int c,n;
    while(scanf("%d%d",&c,&n))
    {
        if(c==0&&n==0) break;
        for (int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            u[i]=-1;               //1-n的点都设为-1（不包括0）
        }
        long long sum=0;
        for (int i=1;i<=n;i++)
        {
            sum+=a[i];
            if(u[sum%c]!=-1)
            {
                for (long long j=u[sum%c]+1;j<=i;j++)
                {
                    printf("%lld",j);
                    if(j!=i) cout << " ";
                }
                cout << endl;
                break;
            }
            u[sum%c]=i;
        }
    }
    return 0;
}