AtCoder ABC 142 D - Disjoint Set of Common Divisors (Go) - あるエンジニアのAtCoder奮闘記

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

問題

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

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回取り扱うことになるかもしれません。