Python3で解く AtCoder Beginner Contest 142 D - Disjoint Set of Common Divisors

公約数と互いに素の問題

---

概要

問題

1. 1以上の2つの整数を与えるので、公約数からいくつか選ぶ。
2. ただし、選んだもののどの2組も互いに素である必要がある。
3. 最大いくつ選ぶことができる？

---

解くときに考えた内容

• 公約数って約数列挙からのset？
  うーん、ちょっとパターン多いしちょっと後回し。
• いくつか選んだ公約数のうち２つえらんで全てで互いに素になるようにしたときの最初にいくつか選ぶことができるかの最大数。
  これって、いくつか選んだ公約数が1か素因数でないと成立しない 例えば、2, 3, 5とは選べるが、2, 3, 5, 6とは選べない。
  6は2, 3の倍数なので6を選んだら2, 3を消すことになり、素因数じゃないものを選ぶなら、それを構成する素因数を選んだ方が選ぶことができる数は大きくなる。

ということで、の共通の素因数を出して、1も約数なので数に加えるということでよい。

解説見て後から気づいたが、がと の公約数であることと、が の約数であることは同値ということで公約数から考えるっていう方法もあったみたいだが、自分的にはすべて2組が互いに素にならなきゃいけない条件から考えた方が考えやすかった。

素因数分解

結構使う場面が多いので関数化している。

• までを増加させながらの時にで割れるだけ割ってしまう。
• これによって、素数の定数倍は条件に合わなくなるので素数の組と割れる回数を取得する。
  例えば、[[2, 3], [3, 1],[5, 3]]のように素数と割れる回数を取得できる。
• 今回は回数は不要なので、 [2, 3, 5]のようにユニークな素数の組だけを取得するように若干変形させている。
• までを増加させてforで回すということを書くには、いろんなやり方がある。
  • 自分は直感的にわかりやすいwhile i*i ≦ nを採用。（）
  • 人によってはfor i in range(2, int(-(-tmp**0.5//1))+1)

---

コード

def main():

    def factorization(n):
        # 今回は完全な素因数分解ではなく、  
        # どんな素因数があるかだけで十分なので、  
        # カウント部分は省略
        l = []
        tmp = n
        i = 2
        while i*i <= n:
            if tmp%i == 0:
                # cnt = 0
                while tmp%i == 0:
                    # cnt += 1
                    tmp //= i
                # l.append([i, cnt])
                l.append(i)
            i += 1
        if tmp != 1:
            # l.append([tmp,1])
            l.append(tmp)
        if l == []:
            if n != 1:
                # l.append([n, 1])
                l.append(n)
        return l

    a, b = map(int, input().split())
    a_f = factorization(a)
    b_f = factorization(b)
    # 1も約数なのでその分1加えるのを忘れずに
    ans = len(set(a_f) & set(b_f)) + 1
    print(ans)
    
if __name__ == '__main__':
    main()