ベスパリブ

プログラミングを主とした日記・備忘録です。ベスパ持ってないです。

ABC 142: D問題の解説 (Python3)

Python AtCoder 競技プログラミング 数学問題

問題：AtCoder Beginner Contest 142: D - Disjoint Set of Common Divisors

公式解説PDF：https://img.atcoder.jp/abc142/editorial.pdf

公式解説動画：AtCoder Beginner Contest 142 - YouTube

解説

要約すると、（gcd(A, B)を素因数分解したときの素因数の個数）+1が答え。

入力例2を考えます。

「420と660の正の公約数の中からいくつか約数を選んで、選んだやつのどの異なる2つの整数も互いに素となる最大の約数の個数は何か？」という問題になります。

420と660の正の公約数は、必ず最大公約数以下の値になります。よって約数のとりうる範囲は1 ~ 最大公約数になります。420と660 の最大公約数gcd(420, 660)は60です。

60の約数を列挙してみます。

1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

このうち、どの2つの整数も互いに素となる約数の個数が最大となる選び方は、

1, 2, 3, 5 の4つです。

見やすく表にして整理すると、

60の約数 1 2 3 4 5 6 10 12 15 20 30 60
答え 1 2 3 5

たとえば15はなぜいけないのでしょうか？それは15を素因数分解すると 15 = 3^1 * 5^1 なので、15を選ぶと3と5が選べなくなってしまいます。 よって15を選ぶより3と5を選んだほうが多くを選べるということになります。

12や20なんかも同様の理由で選べません。

4はどうでしょうか？これは素因数分解すると 4 = 2^2になります。つまり4を選ぶと2を選べなくなります。この2を選ばないパターンの1 3 4 5は、どの2つの整数も互いに素となっているのでOKです。よって2の代わりに4を選ぶのはありですが、選ぶメリットは特にないですよね。素数しか選ばないというルールのほうが問題を簡単化できます。

ということで入力例2の場合では、gcd(420, 660)で最大公約数を求めて、その最大公約数を素因数分解したときの素因数を選べば、どの2つの整数も互いに素となります。あとついでに1も約数なのでこれも加えます。これが答えになります。

制約 A, B \leqq 10^{12}を考えます。Nがでかすぎるので、 O(N)の解法はTLEします。

この問題におけるNとは、AとBの最大公約数gcd(A, B)の値です。1～gcd(A, B)の範囲で素因数を数えることになります。gcd(A, B)の最大値は 10^{12}なので、 O(N)は無理です。

ですが実は、最大公約数Nが何かの整数pで割り切れるときは、 N = p * q と書けますので、 p \leqq \sqrt{N}となります（例： N=10^{12} のとき、 p=10^6、 q=10^6 ）。なのでNまで調べる必要はなく、 O(\sqrt{N})で解くことができます。

このあたりの考え方はエラトステネスの篩とかで素数を数える問題を知っていて慣れていれば、 O(\sqrt{N})で解けそうだなと当たりがつきます。

コーナーケース

  • 最大公約数が1のとき、1を出力して終了

実装

# -*- coding:utf-8 -*-
import sys
from fractions import gcd
from collections import Counter


def prime_factorization(n):
    """nを素因数分解する

    Return d(dict):
        素因数をキー、素因数の指数部を値とするディクショナリを返す

    Example:
        n=140 -> d = {2: 2, 5: 1, 7: 1}
    """
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m = m + 1 if m == 2 else m + 2  # m=3からは、m+=2する（偶数は明らかに素数ではないので）

    if n > 1:
        d[n] += 1
    return d


def solve():
    A, B = list(map(int, sys.stdin.readline().split()))
    cd = gcd(A, B)

    if cd == 1:  # コーナーケース
        print(1)
        return

    # (素因数分解の素因数の個数)+1が答え
    prime_d = prime_factorization(cd)
    print(len(prime_d)+1)


if __name__ == "__main__":
    solve()

計算量は O(\sqrt{N})です 。

蛇足

なんか偉そうに「この問題に慣れていれば～」とか書きましたが、本番でTLEしてるんですよね。精進します。