Halloween treats（鸽巢定理）

Halloween treats

题意

有c个小朋友，n户家庭，n户家庭中每户分别有$a_i$个糖果，小朋友们可以向任意户家庭讨糖果，最终的糖果被小朋友平均分，问你向哪几户人家讨糖果可以使得平均分成立？（任意输出即可）

如果没有输出“no sweets”。

1<=c<=n<=100000

思路

鸽巢定理的应用。

对于正整数序列，$a_1，a_2，…，a_m$，至少存在整数k和l,1<=k<l<=m，使得$a_k+a_{k+1}+…+a_l$是m的倍数。（证明见容斥和鸽巢定理介绍）

因此对每个数i求前缀，第一，如果前缀本身就能被c整除，那么输出1~i，否则，sum[i]%=c；第二，如果有任意两个sum[i],sum[j]对c取模后相等，则证明$a_{i+1}到a_j$的数之和是c的倍数。输出这几个数即可。

注意，这个定理的条件是c不大于n。

看！代码

#include <bits/stdc++.h>
using namespace std;
int a[100010];
int sum[100010];
int main()
{
    int n,c;
    while(~scanf("%d%d",&c,&n))
    {
        if(c==0&&n==0) break;
        a[0]=0;
        int flag=-1;
        vector<int>same[c+1];
        memset(sum,0,sizeof(sum));
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
        {
            sum[i]=sum[i-1]+a[i];
            if(sum[i]%c==0)
            {
                flag=0;
                same[0].push_back(0);
                same[0].push_back(i);
                break;
            }
            sum[i]%=c;
            same[sum[i]].push_back(i);
            if(same[sum[i]].size()==2)
            {
                flag=sum[i];
                break;
            }
        }
        if(flag==-1)
        {
            puts("no sweets");
            continue;
        }
        int a=same[flag][0],b=same[flag][1];
        for(int i=a+1;i<b;i++)
            printf("%d ",i);
        printf("%d\n",b);
    }
    return 0;
}