数学–数论–鸽巢原理

鸽巢原理：

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

鸽巢原理又叫抽屉原理,球盒原理。

推广：

如果要把n个物件分配到m个容器中，必有至少一个容器容纳至少⌈n / m⌉个物件。（⌈x⌉大于等于x的最小的整数）

poj2356 Find a multiple（抽屉原理）

题目大意就是先给出一个数N，接着再给出N个数，要你从这N个数中任意选择1个或多个数，使得其和是N的倍数

如果找不到这样的答案则输出0

答案可能有多个，只用任意输出一个解就行。

输出的第一行是选择元素的个数M，接着M行分别是选择的元素的值

由鸽笼原理可知此题一定有解，不存在输出0的结果

分析：

我们可以依次求出a[0],a[0]+a[1],a[0]+a[1]+a[2],…,a[0]+a[1]+a[2]…+a[n]；

假设分别是sum[0],sum[1],sum[2],…,sum[n]

如果在某一项存在是N的倍数，则很好解，即可直接从第一项开始直接输出答案

但如果不存在，则sum[i]%N的值必定在[1,N-1]之间，又由于有n项sum，有抽屉原理：

把多于n个的物体放到n个抽屉里，则至少有一个抽屉里有2个或2个以上的物体。
则必定有一对i，j，使得sum[i]%N=sum[j]%N，其中i！=j，不妨设j>i

则（sum[j]-sum[i]）%N=0，故sum[j]-sum[i]是N的倍数

则只要输出从i+1～j的所有的a的值就是答案

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
int n,a[10010],sum,sum0;
bool vis[10010]={0};int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);vis[0]=1;sum=0;for(int i=1;i<=n;i++){sum+=a[i];sum%=n;if (vis[sum]){sum0=0;int s,t=i;if (sum0==sum) s=1;else{for(int j=1;j<=n;j++){sum0+=a[j];sum0%=n;if (sum0==sum) {s=j+1;break;}}}printf("%d\n",t-s+1);for(int j=s;j<=t;j++)printf("%d\n",a[j]);break;}else vis[sum]=1;}return 0;
}