bzoj 3837 pa2013 Filary

bzoj

先搞第一问.考虑简单情况,如果\(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;
}