# ARC118-C Coprime Set

diff11
https://atcoder.jp/contests/arc118/tasks/arc118_c

## 解法

$N = 3$のとき、$S = ( 6, 10, 15 )$は条件を満たす。

$N \gt 3$のときも$S$に値を追加することで構築することを目指す。$\gcd(6, 10, 15) = 1$のため、何を追加しても$\gcd(S) = 1$である。素因数$2, 3, 5$から2種類以上の素因数を含む値を追加し続けると$i\ne j\rightarrow \gcd(S_i, S_j)\gt 1$を満たす。

この方針で構築できる最大サイズは2663であるようだ。制約$N\le 2500$の範囲内で構築することができた

## 実装

#include <bits/stdc++.h>

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    const int MAX{10001};

    std::vector<int> A;
    std::vector<bool> vis(MAX);
    auto dfs{[&](auto dfs, int v) -> void {
        A.push_back(v);
        vis[v] = true;
        for (int i{2} ; i * v <= MAX ; i++) if (!vis[i * v])
            dfs(dfs, i * v);
    }};
    for (auto v : { 2 * 3, 2 * 5, 3 * 5 }) {
        for (int i{2} ; i * v <= MAX ; i++) if (!vis[i * v]) 
            dfs(dfs, i * v);
    }
    // dfs(dfs, 2 * 3);
    // dfs(dfs, 2 * 5);
    // dfs(dfs, 3 * 5);
    std::sort(A.begin(), A.end());
    A.erase(std::unique(A.begin(), A.end()), A.end());
    int N;
    std::cin >> N;
    N -= 3;
    std::cout << 2 * 3 << ' ' << 2 * 5 << ' ' << 3 * 5;
    for (int i{} ; i < N ; i++) std::cout << ' ' << A[i];
    std::cout << '\n';
}

[提出リンク](https://atcoder.jp/contests/arc118/submissions/58042088)

## 感想

めっちゃ時間かかった。構築苦手だし嫌いだ....