题解 CF364D 【Ghd】

· · 题解

题意简述：

输入 n\ (1≤n≤10^6) 及 n 个整数 a_1,a_2,...a_n\ (1≤a_i≤10^{12}), 请从中取出 \lceil \frac{n}{2} \rceil 个数，使得它们的 gcd (最大公约数) 最大，输出最大的 gcd。

本题用到要随机化，需要随机化10次，再多就有可能 T 了，这样出错的概率就是 1-\frac{1}{2^{10}}，也就是 \frac{1}{1024}，但是说实话这个概率真的不低，我第一次提交就 WA 了。

每次随机化，从输入的数中取出一个数 x，然后进行因数分解，用 d 数组从小到大存 x 的因数，再用 cnt_i 表示输入的 n 个数中有几个数含有因数 d_i，最后直接从大到小判断每个 d_i，如果 cnt_i×2≥n，也就是含有 d_i 这个因数的数的个数 ≥\lceil \frac{n}{2} \rceil 那么 d_i 就是最终要求的答案。

在求 cnt_i 时，要把 n 个数枚举一遍，每次找到 gcd(x,a_i) 在 d 数组中的位置 pos 然后 cnt_{pos}++。

for(int i=1; i<=n; i++)
{
    int pos=lower_bound(d+1,d+1+siz,gcd(x,a[i]))-d; //找到d数组中第一个>=gcd(x,a[i])的数的位置。
    cnt[pos]++;
}

做完这个之后，还要知道如果 d_j\mod d_i=0，那么 cnt_i+=cnt_j，因为上一步我们只对 gcd 进行了计数，然而我们要对每个因数进行计数。

最后，题目上提到建议使用%I64d，我也不太清楚这个，应该是只能在Windows上用，但是不用应该也没关系，用 long\ long 就可以了。

代码应该还算简洁

#include<iostream>
#include<cstdio>
#include<time.h>
#include<stdlib.h>
#include<cmath>
#include<algorithm>
#include<cstring> 
#define ll long long

using namespace std;

const int maxn=1e6+10;
int n,siz;
ll d[maxn],a[maxn],cnt[maxn];

ll gcd(ll x,ll y)   //最大公因数 
{
    return !y?x:gcd(y,x%y);
}

int random(int l,int r) //在l~r的范围内随机化取数 
{
    return (ll)rand()*rand()%(r-l+1)+1;
}

void divide(ll x)   //对x进行分解因数 
{
    siz=0;
    for(ll i=1; i*i<=x; i++)
        if(x%i==0)
        {
            d[++siz]=i;
            if(x/i!=i) d[++siz]=x/i;
        }
}

int main()
{
    srand(time(NULL));  //随机化种子 
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%I64d",&a[i]);
    ll ans=0;
    for(int cas=1; cas<=10; cas++)
    {
        ll x=a[random(1,n)];
        divide(x);
        sort(d+1,d+1+siz);  //排序，这样才能用二分 
        memset(cnt,0,sizeof(cnt));
        for(int i=1; i<=n; i++)
        {
            int pos=lower_bound(d+1,d+1+siz,gcd(x,a[i]))-d; //找到d数组中第一个>=gcd(x,a[i])的数的位置。
            cnt[pos]++;
        }
        for(int i=1; i<=siz; i++)
            for(int j=i+1; j<=siz; j++)
                if(d[j]%d[i]==0)
                    cnt[i]+=cnt[j];
        for(int i=siz; i>=1; i--)
            if(cnt[i]*2>=n) //第一个符合题意的，同时也是最大的 
            {
                ans=max(ans,d[i]);
                break;
            }
    }
    printf("%I64d\n",ans);
    return 0;
}