Author: lllyouo
Date: 20250702
tag: 约数、最大公约数
link: https://www.luogu.com.cn/problem/P1414

问题描述

link

分析

当 $k$ 不断变大时，则它们的最大公约数相应的会变小，这是因为有：

$$gcd(a,b)=p_1^{min(a_1,b_1)}\cdot p_2^{min(a_2,b_2)}\cdot \cdots \cdot p_k^{min(a_k,b_k)}$$

可知：$gcd(a,b,c)\le gcd(a,b)$

本题中可使用数组 cnt[i] 记录数字 $i$ 可以作为最大公约数的数字的数量。

当求 $k$ 时的答案，只需要从 $inf$ 开始遍历，直到找到 $cnt[i]\ge k$ 且最大的一个即可。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
int n, cnt[N];

int main() {
    cin >> n;

    int maxv = 0;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        maxv = max(maxv, x);
        for (int j = 1; j * j <= x; j++) {
            if (x % j == 0) {
                cnt[j]++;
                if (j != x / j) cnt[x / j]++;
            }
        }
    }

    int ans = maxv;
    for (int i = 1; i <= n; i++) {
        while (cnt[ans] < i) ans--;
        cout << ans << endl;
    }
    
    return 0;
}