题解 | #E D 与太阳#

本人的第一篇题解
思路全在代码里了,也尽可能地写了详细的注释

//题意：对n个数a[i]（sum<=1e13）,选定j和k使得满足a[i]%j==k的数最多
//思路：a[i]%2==0or1,所以至少(n+1)/2个答案
//随机x和y,1/4的可能性在答案内，x%j==y%j,(x-y)%j=0
//d=x-y,对d质因数分解,这些都是可能的j，加入集合s
//对s的每个元素j随机x,1/2的可能性a[x]在答案内，a[x]%j就是可能的k
//如果a[x]%j=k的次数大于某个数，说明是可能的答案
//按以上流程选定j和k进行计算:枚举a[1]~a[n],统计a[i]%j==k的个数ansnow
//对于每个选定的j和k,ans=max(ans,ansnow)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7;
ll a[N];
ll p[N],cnt;
ll res[N];
bool ifp[N];
set<ll>s;
void init()
{
    ll i,j;
    for(i=2;i<N;i++)
    {
        if(ifp[i])continue;
        p[++cnt]=i;
        for(j=i+i;j<N;j+=i)
            ifp[j]=1;
    }
}
inline ll read(){
	ll s=0,w=1;
	char c=getchar();
	while(!isdigit(c)) w=-1,c=getchar();
	while(isdigit(c)) s=s*10+(c^48),c=getchar();
	return s*w;
}
int main(){
    srand((unsigned)time(NULL));
    init();
    ll n,i,j;
    n=read();
    for(i=1;i<=n;i++)
        a[i]=read();  //请注意本题读入量较大,不用快读可能会超时
    ll t=30; //随机次数
    ll x,y,d;
    map<ll,bool>visd;
    while(t--)  //有1/4的可能这两个包含在答案内
    {
        x=rand()%n+1;
        y=rand()%n+1;
        if(x==y)continue;
        d=abs(a[x]-a[y]);
        if(visd.find(d)!=visd.end())
            continue;
        visd[d]=1;
        for(i=1;i<=cnt;i++)
        {
            if(d==1)break;
            if(d%p[i]==0) //是差的质因子，求对应答案
            {
                s.insert(p[i]);
                while(d%p[i]==0)d=d/p[i];
            }
        }
        if(d!=1)
            s.insert(d);
    }
    s.insert((ll)2); //2很有可能是答案，保底
    //下面对每种可能的因子进行答案计算,复杂度o(s.size()*t*n*10)
    ll ans=0,ansnow,k;
    map<ll,ll>mp; //记录a[i]%k的个数,越多是答案的可能性越大
    for(auto j:s)
    {
        mp.clear(); //每个不同
        t=2000;     //随机a[i]/j,有1/2的可能a[i]在答案内
        while(t--)
        {
            x=rand()%n+1;
            k=a[x]%j;
            mp[k]++;
            if(mp[k]==200) //出现次数较多，才会进行计算
            {
                ansnow=0;
                for(i=1;i<=n;i++)
                {
                    if(a[i]%j==k)
                        ansnow++;
                }
                ans=max(ans,ansnow);
            }
        }
    }
    ans=max(ans,(n+1)/2); //至少(n+1)/2个，保底
    printf("%lld\n",ans);
}