BZOJ

分析

首先我们可以得到 $k$ 至少为 $\frac{n}{2}$，构造方式是令 $m=2$。

也就是说，在最优解中每个数被选中的概率是 $>\frac{1}{2}$ 的。

考虑 rand() 一个在最优解中的数 $x$，我们把其它的 $\neq x$ 的数与 $x$ 作差并分解质因数，那么所有质因数中出现次数的最大值加上 $=x$ 的数的数量就是当前最大的 $k$。

这里有一个 trick 是我们可以通过预处理出每个数的最小质因子来 $O(\log n)$ 分解质因数。

然后就没有了，可以适当的卡一下时。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,V=10000000+10;

int v[V],p[V],mp[V],cnt=0;
inline void sieve(int n) {
    for (re int i=2;i<=n;++i) {
        if (!v[i]) p[++cnt]=i,mp[i]=cnt;
        for (re int j=1;j<=cnt&&i*p[j]<=n;++j) {
            v[i*p[j]]=1,mp[i*p[j]]=j;
            if (i%p[j]==0) break;
        }
    }
}

int n,a[N],c[N];
int s[V],d[V];

int main() { sieve(1e7); srand(19491001);
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read();
    int ansk=0,ansm=0;
    do { memset(s,0,sizeof(s)),memset(d,0,sizeof(d));
        int x=a[rand()%n+1];
        for (re int i=1;i<=n;++i) {
            c[i]=abs(a[i]-x);
            if (c[i]==0) ++s[0];
        }
        int nowk=0,nowm=0;
        for (re int i=1;i<=n;++i) {
            int t=c[i];
            while (t>1) { int v=mp[t];
                ++s[v],d[v]=__gcd(d[v],c[i]);
                if (s[v]+s[0]>nowk) nowk=s[v]+s[0],nowm=d[v];
                else if (s[v]+s[0]==nowk) nowm=max(nowm,d[v]);
                while (t%p[v]==0) t/=p[v];
            }
        }
        if (nowk>ansk) ansk=nowk,ansm=nowm;
        else if (nowk==ansk) ansm=max(ansm,nowm);
    } while (1.0*clock()/CLOCKS_PER_SEC<0.8);
    printf("%d %d\n",ansk,ansm);
    return 0;
}