ABC142 D - Disjoint Set of Common Divisors

問題原文

atcoder.jp

問題要旨

, の公約数からなる集合であって、どの２数についても互いに素が成り立つようなものの最大の大きさを求めよ。

• 

解法

４とか選んじゃうと、結局素因数に２を持つような数がもう選べなくなってしまう。結局これは２を選ぶのと変わらない。
でも、２が選べて４が選べないパターン（（12, 18）とか）があるので、２を選ぶ方が損しない。
結局素数集めればいいじゃんとなって、終わり。１がOKなことには注意。

実装

素因数分解 → 集合が楽だと思う
エラトステネスの篩とかで予め素数全列挙とかしようとすると、ちょっとめんどくさいことになりそうかな（知らんけど）

A, B = map(int, input().split())


def prime_factorization(n):
    table = []
    for x in range(2, int(n ** 0.5) + 1):
        while n % x == 0:
            table.append(x)
            n //= x
    if n > 1:
        table.append(n)
    return table


A_factor = set(prime_factorization(A))
B_factor = set(prime_factorization(B))
print(len(A_factor & B_factor) + 1)

感想

素数集めたら良さそうだなと思ったら、素数集めればよかった。
証明も、「損しない」というキーワードを元に考えれば思いつける。