ABC142-D

AtCoder Beginner Contest 142のD問題の解説です。

問題の詳細は公式の問題ページをご確認ください。

問題文

正整数A,Bが与えられます。 AとBの正の公約数の中からいくつかを選びます。 ただし、選んだ整数の中のどの異なる2つの整数についても互いに素でなければなりません。 最大でいくつ選べるでしょうか。

制約

  • 入力は全て整数である
  • 1 ≤ A,B ≤ 10^{12}

入力

A B

出力

条件を満たすように選べる整数の個数の最大値を出力せよ。

解説

毎回、問題文を勘違いしやすいのですが、A,Bの公約数の作る集合の有限部分集合であって,任意の異なる2要素が互いに素となるようになるものを考える.その中で要素の数の最大値を求めればよいです.

まずA,Bの公約数は最大公約数の約数です. なので最大公約数の約数たちの中で条件を満たすものを選べばよいです。

個数が最大になる場合は,各要素は素数のべき乗になります。 なぜなら上の条件を満たす集合Sに対し,素数のべきでない要素xが存在したとします。 この時2つの互いに素な数y,zを使いx = yzとできます。 よってS - {x} + {y, z}を考えればこれはSよりも真に要素が大きくなります。

これからSは素数のべきしか要素がありません。 さらにSは最大の場合、最大公約数を割り切る素数のべきじょうの要素は全て入り、この時最大となります。

これから最大公約数を割り切る素数の個数が求める解になります。

それを計算すると以下になります。

from fractions import gcd
A, B = list(map(int, input().split()))

C = gcd(A, B)


def prime_factorize(n):
    a = {}
    while n % 2 == 0:
        a[2] = True
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a[f] = True
            n //= f
        else:
            f += 2
    if n != 1:
        a[n] = True
    return a

print(len(prime_factorize(C)) + 1)

pythonで実装する場合の注意

  • gcdの計算方法
    gcdはmathモジュールにありますが、2020年3月現在AtCoderがサポートするpython 3.4.3では, fractionsモジュールを使う必要があります。

  • コピペの注意
    Pythonはインデントがずれるとエラーになります。 ローカルからのコピペミスで一回実行エラーに。。。 気をつけましょう。

// コードブロック