【ABC142 D】「Disjoint Set of Common Divisors」を解く【Python3】

正の整数A,Bの公約数の中から選んだ数字が、他のどの公約数とも互いに素であるか調べ、互いに素である公約数の個数を答える問題です。

提出

def prime_factorization(n):
    i = 2
    li = []
    while i*i <= n:
        while n%i == 0:
            li.append(i) 
            n /= i
        i += 1
    if n > 1:
        li.append(int(n))
    return li

a, b = map(int, input().split())
ap = prime_factorization(a)
bp = prime_factorization(b)

print(len(set(ap) & set(bp))+1)

2つの数字のそれぞれの約数を求め、どちらにも存在するものが、公約数となります。

入力例1の記述の通り、12と18の公約数は、[1, 2, 3, 6]です。

6は、2でも3でも割り切れてしまうので、これが除外したものが答えになります。

そこで、それぞれの約数ではなく、それぞれの素因数を求め、どちらにも存在するものの個数を調べます。

下記の部分で、素因数分解しています。

def prime_factorization(n):
    i = 2
    li = []
    while i*i <= n:
        while n%i == 0:
            li.append(i) 
            n /= i
        i += 1
    if n > 1:
        li.append(int(n))
    return li

返ってきたリストliの中身の重複を消すために、set()で重複のない集合にします。

print(len(set(ap) & set(bp))+1)

12の素因数は[2, 3]、18の素因数は[2, 3]となり、どちらにも[2, 3]があります。

1も互いに素である要素に加わるため、1つ増えて、個数は3個になります。

入力例2では、

420の素因数[2, 3, 5, 7]と、660の素因数[2, 3, 5, 11]にある、[2, 3, 5]と1が条件に当てはまるため、答えは4となります。

このほか、最大公約数(gcd)を先に求める方法があります。

提出

import math

a, b = map(int, input().split())
n = math.gcd(a, b)
i = 2
li = []

while i*i <= n:
    while n%i == 0:
        li.append(i)
        n /= i
    i += 1
if n > 1:
    li.append(int(n))

print(len(set(li))+1)

最大公約数の素因数を求め、それに1を足したものが答えになります。

入力例2を用いると、420と660の最大公約数は60、この素因数は[2, 3, 5]となり、これに1を加えたものが答えになります。