bzoj 3837 pa2013 Filary

先搞第一问.考虑简单情况,如果\(m=2\),那么一定有个剩余类大小\(\ge \lceil\frac{n}{2}\rceil\),同时这也是答案下界

然后我们每次随机选出一个数\(a_i\),然后钦定它在我们要的剩余类里,现在再枚举其他数,看一下最多有多少个数\(a_j\)可以和他模\(m\)同余,也就是选最多的数满足\(\gcd(|a_i-a_{j_1}|,|a_i-a_{j_2}|,|a_i-a_{j_3}|...)>1\).那对于每个\(j\),把所有\(|a_i-a_j|\)的质因子位置全\(+1\)--因为\(m\)取质数显然比取合数优.最后\(cnt_p\)的最大值即为第一问答案

第二问的话,因为是\(\gcd(...)>1\),那我们对于每个质数位置维护\(|a_i-a_j|\)为它倍数的\(\gcd(|a_i-a_j|...)\),这样第二问答案就是第一问最大的位置上最大的这个\(\gcd\)

#include<bits/stdc++.h>

#define LL long long

#define uLL unsigned long long

#define db double

using namespace std;

const int N=1e5+10,M=N*100;

int rd()

{

	int x=0,w=1;char ch=0;

	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}

	return x*w;

}

int n,a[N],prm[N*10],tt,pp[M],a1,a2,c1[M],c2[M];

int main()

{

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

	{

		if(!pp[i]) pp[i]=i,prm[++tt]=i;

		for(int j=1;i*prm[j]<=10000000;++j)

		{

			pp[i*prm[j]]=prm[j];

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

		}

	}

	n=rd();

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

	int Q=10;

	while(Q--)

	{

		int ii=rand()%n+1,bs=0;

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

		{

			if(a[i]==a[ii]){++bs;continue;}

			int x=abs(a[i]-a[ii]),xx=x,las=0;

			while(x>1)

			{

				if(pp[x]!=las)

					++c1[pp[x]],c2[pp[x]]=__gcd(xx,c2[pp[x]]);

				las=pp[x],x/=pp[x];

			}

		}

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

		{

			if(a[ii]==a[i]) continue;

			int x=abs(a[i]-a[ii]);

			while(x>1)

			{

				if(c1[pp[x]]+bs>a1||(c1[pp[x]]+bs==a1&&c2[pp[x]]>a2))

					a1=c1[pp[x]]+bs,a2=c2[pp[x]];

				c1[pp[x]]=c2[pp[x]]=0;

				x/=pp[x];

			}

		}

	}

	printf("%d %d\n",a1,a2);

    return 0;

}

巴特西

bzoj 3837 pa2013 Filary

最新文章

热门文章