7K12 blog

猫でも分かる何か

ABC142 D - Disjoint Set of Common Divisors

f:id:tkr987:20200722022734p:plain

https://atcoder.jp/contests/abc142/submissions/15352890

https://atcoder.jp/contests/abc142/submissions/15351653

f:id:tkr987:20200722023637p:plain

「互いに素でなければならない」という条件から何となく素数がポイントになりそうという気持ちになる。実際、gcd(A, B)を素因数分解したものが答えになる。

AとBの公約数 ⇔ gcd(A, B)の約数 であり、約数の個数が素因数分解 a^i \times b^j \times c^k ... したときの (i+1)(j+1)(k+1)... であることから、gcdを素因数分解した因数の組み合わせが約数ということになる。そのうち素数となる数字の個数が答えなので a_1^i \times a_2^j \times ... \times a_{n}^k の因数の個数 n を出力すれば良い（正確には1を含むのでn+1を出力する）。なお、gcdの約数のうち素数となる数字の個数が答えになる理由は、素数以外を選ぶと「互いに素」条件で選べる数字が減ってしまうためである。

また、gcdの素因数分解に気づかなかったときの別解として、約数の個数が \log N程度なので公約数を列挙して素数判定する方法でも間に合う。この実装の場合、約数が 10^6を超えるテストケースが存在するので、素数テーブルを使わずに各約数に対して O(\sqrt N)で素数判定すること。