【BZOJ3837】[Pa2013]Filary

Description

给定n个正整数，从中挑出k个数，满足：存在某一个m(m>=2)，使得这k个数模m的余数相等。

求出k的最大值，并求出此时的m。如果有多组解使得k最大，你要在此基础上求出m的最大值。

Input

第一行一个正整数n（2<=n<=10^5)。

第二行n个正整数w[i](1<=w[i]<=10^7)。保证不会出现所有w[i]都相等的情况。

Output

一行两个整数k,m。保证答案存在。

Sample Input

6
7 4 10 8 7 1

Sample Output

5 3

题解：我们随机选取一个数x，然后将所有数与它作差，那么只需要找出k个差值使得他们的gcd>1即可。我们可以将所有差值分解质因数，然后统计每个质因数出现的次数，再加上与x相等的数的个数就是k。统计k个时候顺便记录一下这些数的gcd即可。

本题还有一个特殊性质，当m=2时，k一定>n/2。所以我们期望随机log次就能得到一个选中的数了。（实际情况根据随机的种子而定，一开始自己设的种子要么奇慢无比，要么WA，后来把种子去掉，随机4次就行了。）

#include <cstdio>

#include <iostream>

#include <cstring>

#include <cstdlib>

using namespace std;

const int maxn=100010;

int n,x,nk,nm,k,m,num;

int pri[1000010],lp[10000010],s[1000010],g[1000010];

bool np[10000010];

int v[maxn],c[maxn];

int rd()

{

	int ret=0;	char gc=getchar();

	while(gc<'0'||gc>'9')	gc=getchar();

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret;

}

int gcd(int a,int b)

{

	return (!b)?a:gcd(b,a%b);

}

int main()

{

	int i,j,T;

	for(i=2;i<=10000000;i++)

	{

		if(!np[i])	pri[++num]=i,lp[i]=num;

		for(j=1;j<=num&&i*pri[j]<=10000000;j++)

		{

			np[i*pri[j]]=1,lp[i*pri[j]]=j;

			if(i%pri[j]==0)	break;

		}

	}

	n=rd();

	for(i=1;i<=n;i++)	v[i]=rd();

	for(T=1;T<=4;T++)

	{

		x=v[rand()%n+1];

		for(s[0]=0,i=1;i<=n;i++)

		{

			c[i]=abs(v[i]-x);

			if(!c[i])	s[0]++;

		}

		nk=0;

		for(i=1;i<=n;i++)

		{

			int t=c[i];

			while(t&&t!=1)

			{

				int tmp=lp[t];

				s[tmp]++,g[tmp]=gcd(g[tmp],c[i]);

				if(nk<s[tmp]+s[0])	nk=s[tmp]+s[0],nm=0;

				if(nk==s[tmp]+s[0])	nm=max(nm,g[tmp]);

				while(t%pri[tmp]==0)	t/=pri[tmp];

			}

		}

		if(nk>k)	k=nk,m=0;

		if(nk==k)	m=max(m,nm);

		for(i=1;i<=n;i++)

		{

			int t=c[i];

			while(t&&t!=1)

			{

				int tmp=lp[t];

				s[tmp]=g[tmp]=0;

				while(t%pri[tmp]==0)	t/=pri[tmp];

			}

		}

	}

	printf("%d %d",k,m);

	return 0;

}

巴特西

【BZOJ3837】[Pa2013]Filary 随机化神题