ntk log ntk

競プロや非競技プロのやったことを書いています.

ABC142 D - Disjoint Set of Common Divisors

D - Disjoint Set of Common Divisors

思考過程も含めて、自分の解法を書きます。
あまり証明などはしません。きちんとした解説が読みたい方は、公式や他の記事を読んでください。

解法

やりたいことは、公約数の中から条件を満たすように整数をできるだけ多く選ぶことです。
条件は、選んだ整数の中でどの異なる2つの整数も互いに素であることです。
とりあえずAとBの約数をそれぞれ作り、その積集合を取ることでAとBの公約数を作ります。
AとBをsetで持っておくと、&演算子かintersection()で積集合が取れます。
ここで、入力例2の公約数を出力してみました。見やすいようにソートをします。
[1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]
1は他のどの整数とも互いに素なので必ず選ばれる、2を選ぶとそれ以降の偶数が選べなくなる。 3を選ぶと、その後の3の倍数が選べなくなる。あたりまで考えて、小さい方から選べる整数を取っていくと上手くいく気がしました。
長さが公約数の個数、初期値が全てTrueのリストAを作ります。forループを回し、A[i]がTrueなら、それ以降のA[i]の倍数をFalseにします。 最終的にAのTrueの数が答えです。forを回すとき、A[i]が1のときはスキップすることに注意してください。

提出コード


公式の解説pdfを見ると、1または素数のみを選んだ最適解が存在するとあります。確かに、上の解法で最終的に選ばれているのは1と素数だけです。4が公約数なら2も公約数、15が公約数なら3も5も公約数、などに思い当れば、素数を取っていこうという気持ちになったかもしれません。しかし[1,6,12,36]のような公約数になることがある気がして(そうなることはない)、上のように解きました。
考察をあまり詰めずに、実装しました。ただ、(公約数の個数)2回ループを回しているところで計算量が不安になり、約数の個数の最大値はここで調べました。