又一道 GCD 问题

题目链接：nowcoder 213804

到主站看：https://blog.csdn.net/weixin_43346722/article/details/112740731

题目大意

给你一个数组，要你求出从他们中选出 个的 gcd 的最大值。

思路

看到这道题，我们考虑看有多少个数有 这个因子，设其为 。

那我们分解一下质因子（用素数筛选法和 floor(sqrt()) 来加速），然后 dfs 一下，就可以得到一个数的每个因子，就从而求出了 。

那有了这个，我们可以求出要选出 个数的 gcd 最大值是多少了。
（就是从后往前搜第一个 大于等于 的数）

那我们可以先弄出刚刚好是 个数的，然后再从后往前跑最大值。

然后就可以得出答案了。

具体实现可以看看代码。

代码

#include<cmath>
#include<cstdio>
#include<iostream>

using namespace std;

int n, a[100001], su[50001], all[100001], tmpn, tmp, ans[100001], maxn, zyz[1001], numm[1001];
bool susu[100100];

void getsusu() {//素数筛选法筛出素数
    susu[1] = susu[0] = 1;
    for (int i = 2; i <= maxn + 100; i++)
        if (!susu[i]) {
            su[++su[0]] = i;
            for (int j = i + i; j <= maxn + 100; j += i)
                susu[j] = 1;
        }
}

void dfs(int now, int sum) {
    if (now == zyz[0] + 1) {
        all[sum]++;
        return ;
    }
    int tmpp = 1;
    for (int i = 0; i <= numm[now]; i++) {//对于这一个因数，选多少个乘
        dfs(now + 1, sum * tmpp);
        tmpp *= zyz[now];
    }
}

int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        maxn = max(maxn, a[i]);
        ans[i] = 1;
    }

    getsusu();

    for (int i = 1; i <= n; i++){
        zyz[0] = 0;//分解质因数
        tmpn = a[i];
        tmp = floor(sqrt(a[i]));
        for (int j = 1; su[j] <= tmpn && j <= tmp; j++) {
            if (tmpn % su[j] == 0) {
                zyz[++zyz[0]] = su[j];
                numm[zyz[0]] = 0;
                while (tmpn % su[j] == 0) {
                    numm[zyz[0]]++;
                    tmpn /= su[j];
                }
            }
        }

        if (tmpn != 1) {
            zyz[++zyz[0]] = tmpn;
            numm[zyz[0]] = 1;
        }

        dfs(1, 1);//标记每一个因数
    }

    for (int i = maxn; i >= 1; i--) {
        if (ans[all[i]] == 1) ans[all[i]] = i;
    }

    for (int i = n - 1; i >= 2; i--)//选 i 个也可以在 i+x 个中选 i 个，不一定要刚刚好
        ans[i] = max(ans[i + 1], ans[i]);

    for (int i = 2; i <= n; i++) printf("%d ", ans[i]);

    return 0;
}