组合数学——鸽巢原理及其应用

    所谓鸽巢原理，即n+1只鸽子，只有n个巢，则至少有一鸽巢有两只鸽子。

    鸽巢原理理解起来并不困难，有些题目需要转换一下。

    POJ3770

    题意：有n个数，可能相同也可能不相同，从中取出一些数，使它们的和能被c整除(c<=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++)
            scanf("%d",&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;
}