あるエンジニアのAtCoder奮闘記

東京都港区にあるアミフィアブル株式会社のエンジニアが、AtCoderで解いた問題について振り返ったりしていく会社公認のブログです。

AtCoder ABC 142 D - Disjoint Set of Common Divisors (Go)

irisruneです。もう9月も終わりですが、残暑が続きますね。

問題

atcoder.jp

アルゴリズムは単純なので難易度は比較的低いですが、素因数分解が必要なため割と面倒な問題です。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextStr() string {
    sc.Scan()
    return sc.Text()
}

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func gcd(a, b int) int {
    if a < b {
        a, b = b, a
    }
    if a%b == 0 {
        return b
    }
    return gcd(b, a%b)
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    a, b := nextInt(), nextInt()
    gcd := gcd(a, b)

    ans := 1
    gcdCopy := gcd
    for d := 2; d*d <= gcd; d++ {
        if gcdCopy%d != 0 {
            continue
        }
        ans++
        for gcdCopy%d == 0 {
            gcdCopy /= d
        }
    }
    if gcdCopy > 1 {
        ans++
    }
    fmt.Println(ans)
}

2数が互いに素であるとき、2数の最大公約数が1であるということがいえます。そのため、A,Bの正の公約数の中から互いに素なものを選ぶとき、1あるいは素数のみを選ぶことが最適であるといえます。

結局A,Bの正の公約数はA,Bの最大公約数の約数であるため、A,Bの最大公約数を素因数分解することで解を求めることができます。

なお、素因数分解は2から\lfloor \sqrt{M} \rfloorまでの数でMを割ればいいだけなのですが、ループ回数の基準になる値と除算の対象が同一なので値のコピーを行う必要があったり、最後に残った数が1あるいは(\lceil\sqrt{M}\rceil以上の)素数になることに注意する必要があったり、色々面倒です。

Mが小さければ2からMまでの素数を予め列挙しておくと楽になるのですが、エラトステネスの篩を用いてもO(M\log\log M)の計算量となってしまうので今回はこの手法を用いることができません。妥協して2から\sqrt{M}までの素数を列挙してもあまりメリットはなさそうです。

雑記

  • E問題が厳しいので今週は過去問を2回取り扱うことになるかもしれません。