blog.bouzuya.net

2022-01-05 ARC118 C - Coprime Set を解いた

ARC118 C - Coprime Set を解いた。

問題: https://atcoder.jp/contests/arc118/tasks/arc118_c 解説: https://atcoder.jp/contests/arc118/editorial/1206 参考: https://xenous.hatenablog.com/entry/2021/05/10/011235

  • i != j に対して A_i != A_j かつ gcd(A_i, A_j) > 1 …… (1)
  • gcd(A_1, A_2, ..., A_N) = 1 …… (2)

(1) から A_i は A_j の倍数になっている。 (2) から数列全体では共通部分がない

素数を列挙するのかと思ったけど素数だと (1) を満たせない。 ここで頭が止まってしまって解説を読む。 解説を読んでもいまひとつよく分からないので別の記事を検索して参考 URL に至る。

6, 10, 15 は 2 * 3, 2 * 5, 3 * 5 。

これらの倍数を追加すると条件を満たしながら数列を大きくできる。

数列の最大個数が N (2500) を超えていれば良い。

fn f(set: &mut BTreeSet<usize>, a: usize, b: usize) {
    for x in 1.. {
        if a * x > 10000 {
            break;
        }
        for y in 1.. {
            if a * x * b * y > 10000 {
                break;
            }
            set.insert(a * x * b * y);
        }
    }
}

こういう感じの関数をつくって f(&mut set, 2, 3) てな具合にした。

『セキュア・バイ・デザイン』を読みはじめた。

今日のコミット。