POJ 3370 鸽巢原理

题意：给出n个数 求出任意和 为c的倍数。有多组解输出一组。

这题同POJ2356相似只不过换了个问法，根据鸽巢原理实质上还是一定有解且是连续解。所以只需要求出连续解就可以了。首先用s[1],s[2],s[3]...s[n]表示第一个数到第n个数的和也就是s[n]=a[1]+...+a[n]，然后将s[i]分别对n取余，显然，如果s[i]=0那么此时1-i个数即为n的倍数也就是答案，如果s[i]均不为0，那么通过鸽巢原理可知s[i]个数为n，1<=s[i]<=n-1，那么至少有两个s[i] 即s[i]=s[j] (i!=j) 所以此时i+1至j 即为答案

#include <iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int s[100005],bj[100005];
int main()
{
    int c,n,a,f,ans1,ans2;
    while(~scanf("%d%d",&c,&n),c+n)
    {
        memset(bj,0,sizeof(bj));
        s[0]=f=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%d",&a);
            if(f)
                continue;
            s[i]=(s[i-1]+a)%c;
            if(s[i]==0)
                f=1,ans1=i;
            if(bj[s[i]])
                f=2,ans1=bj[s[i]],ans2=i;
            else bj[s[i]]=i;
        }
        if(f==1)
            for(int i=1; i<=ans1; i++)
                if(i!=ans1)
                    printf("%d ",i);
                else
                    printf("%d\n",i);
        else
            for(int i=ans1+1; i<=ans2; i++)
                if(i!=ans2)
                    printf("%d ",i);
                else
                    printf("%d\n",i);
    }
    return 0;
}