CF1627D Not Adding

传送门

Solution

注意数据范围。用桶记录某数是否在数组内出现。从 $10^6$ 枚举 $x$ 到 $1$，检查是否能生成 $x$。若所有在数组内的 $x$ 的倍数的最大公约数等于 $x$，则可生成 $x$。

设数组内最大的数为 $N$，时间复杂度 $O(N\log N)$

Code

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

const int N = 1e6 + 10;

int f[N], ans, n, maxn;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        f[x] = 1;
        maxn = max(maxn, x);
    }
    for (int i = maxn - 1; i; i--) {
        int gcd = -1;
        if (f[i]) continue;
        for (int j = i + i; j <= maxn; j += i) {
            if (!f[j]) continue;
            if (gcd == -1)
                gcd = j;
            else
                gcd = __gcd(gcd, j);
        }
        if (gcd == i) {
            ans++;
            f[i] = 1;
        }
    }
    printf("%d", ans);
    return 0;
}