程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ2356 Find a multiple 抽屜原理（鴿巢原理）

POJ2356 Find a multiple 抽屜原理（鴿巢原理）

編輯：C++入門知識

題意：給你N個數，從中取出任意個數的數使得他們的和是 N的倍數；

在鴿巢原理的介紹裡面，有例題介紹：設a1,a2,a3,……am是正整數的序列，試證明至少存在正數k和l，1<=k<=l<=m,是的和ak+ak+1+……+al是m的倍數，接下來開始證明：

構造一個序列s1=a1,s2=a1+a2，……，sm=a1+a2+……+am,那麼會產生兩種可能：

1：若有一個sn是m的倍數，那麼定理成立：

2：假設上述的序列中沒有任何一個元素是m的倍數，令rh ≡ sh mod m;其中h=1,2,……,m;我們已知上面的所有項都非m的倍數，得到s1模m的余數是r1,s2模m的余數是r2,同理往下類推，r是一個余數序列，在這裡所有的余數都不為0，因為假設是不存在有m的倍數的，所以r序列的元素小於m，根據抽屜原理（鴿巢原理），m個余數在[1,m-]區間裡的取值至少存在一對rh,rl，並且滿足 rh=rk,即sh和sk滿足

sk ≡ sh mod m，那麼假設h>k，得到

sh-sk = (a1+a2+……+ah) - (a1+a2+……+ak)

sh - sk =ak+1 +ak+2 +……+ah ≡ 0 mod m（此處的k是序列a的下標）

證明到此結束；

那麼熟悉根據抽屜原理（鴿巢原理），稍微動動腦筋便能做這道題目了

先處理出前k個數的sum[k] (1 <= k <= n) 同時對n進行取余操作，如果有一個sum[k]等於0，那麼這個sum就是n的倍數，然後根據鴿巢原理，有n個余數r ,0 <= r <=n ,如果沒有余數0，那麼至少有兩個余數是相同的，即這兩個sum相減得到的差就是n的倍數，

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define eps 1e-7

#define inf 0xfffffff
const ll INF = 1ll<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;
//

int a[100012],mark[1000012],sum[100012];

void clear()
{
	memset(a,0,sizeof(a));
	memset(sum,0,sizeof(sum));
	memset(mark,0,sizeof(mark));
}

int main()
{
	int n;
	while(scanf("%d",&n)==1)
	{
		clear();
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			sum[i] = sum[i-1] + a[i];
			sum[i] %= n;
			mark[i] = 0;
		}
		for(int i=1;i<=n;i++)
		{
			if(sum[i]==0)
			{
				printf("%d\n",i);
				for(int j=1;j<=i;j++)
				{
					printf("%d\n",a[j]);
				}
				break;
			}
			else if(mark[sum[i]])
			{
				printf("%d\n",i-mark[sum[i]]);
				for(int j=mark[sum[i]]+1;j<=i;j++)
					printf("%d\n",a[j]);
				break;
			}
			mark[sum[i]]=i;
		}
	}
	return EXIT_SUCCESS;
}