先搞第一问.考虑简单情况,如果(m=2),那么一定有个剩余类大小(ge lceilfrac{n}{2} ceil),同时这也是答案下界
然后我们每次随机选出一个数(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
",a1,a2);
return 0;
}