ただの技術メモ

個人備忘録

最大公約数と最小公倍数の求め方

競プロでは最大公約数や最小公倍数が度々出題される。

今回は最大公約数や最小公倍数についてまとめてみる。

最大公約数はGreatest Common Divisorを略してgcdやgと表記されることがある。

最小公倍数はLeast Common Multipleを略してlcmやlと表記されることがある。

ユークリッドの互除法と最小公倍数

最大公約数や最小公倍数関連の問題ではユークリッドの互除法をほぼ使うので軽く説明しておく。

ユークリッドの互除法は2つの整数a, bの最小公約数を求めるアルゴリズム。

数IAでやったよね、懐かしい。

以下の手順で最小公約数を求める。

  • b = 0の場合、aを最小公約数とする

  • b = 0でない場合、再帰でbとa をbで割った余りの最小公約数を求める

コードで表現すると以下のようになる。

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

具体例で考える

  1. a = 6, b = 4で考えてみる

この場合、a = 6, b = 4 → a = 4, b = 2 → a = 2, b = 0 となり、最小公約数として2が返される。

  1. a = 4, b = 6で考えてみる

この場合、a = 4, b = 6 → a = 6, b = 4 → a = 4, b = 2 → a = 2, b = 0 となり、最小公約数として2が返される。

このように a と b の大小関係は気にしなくてOK

  1. a = 2, b = 3 で考えてみる

この場合、a = 2, b = 3 → a = 3, b = 1 → a = 1, b = 0 となり、最小公約数として1が返される。

最小公約数が1のとき、「aとbは互いに素」と呼ぶ。

  1. a = 2, b = 0 で考えてみる

この場合、最小公約数として2が返される。

※ 0 = 2 × 0 となるように 2 は 0 の約数の 1つ。

a × b = g × l

最小公倍数は最大公約数を用いて求めることができる。

a, b の最大公約数を g、最小公倍数を l とおくと、

a × b = g × l が成り立つ。

よって

最小公倍数 l = a / gcd(a, b) * b

と表される。

最大公約数を求める問題

以下の最大公約数を求める問題を考えてみる。

atcoder.jp

この問題ではN個の整数からN-1個の整数を選んで最大公約数の最大値を求める。

最大公約数の計算から除く1つの整数の選び方はN通りある。 最大公約数の計算から除く1つの整数を選んで、他の整数の最大公約数を求めると計算量はO(N2)になる。

2≤N≤105なのでこれではTLEしてしまう。

O(N)でこの問題を解くには累積和と似たような考えを使うことできる。

除く整数の左側の整数群の最大公約数を保存しておく配列と右側の整数群の最大公約数を保存しておく配列を作り、それらを利用して最大公約数を求めることで整数を1つ除いて最大公約数を求めることができる。

コードで表現すると以下のようになる。

package main

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

var scanner = bufio.NewScanner(os.Stdin)

func nextInt() int {
    scanner.Scan()                       // トークンの読み込み
    i, e := strconv.Atoi(scanner.Text()) // 読み込んだトークンをTextメソッドで取り出し
    if e != nil {
        panic(e)
    }
    return i
}

func main() {
    scanner.Split(bufio.ScanWords) // 空白区切りで受け取るので引数にbufio.ScanwWordsを渡す
    N := nextInt()
    A := make([]int, N)
    for i := 0; i < N; i++ {
        A[i] = nextInt()
    }

    left := make([]int, N)
    for i := 1; i < N; i++ {
        left[i] = gcd(A[i-1], left[i-1])
    }
    right := make([]int, N)
    for i := N - 2; i >= 0; i-- {
        right[i] = gcd(A[i+1], right[i+1])
    }

    var max int
    for i := 0; i < N; i++ {
        g := gcd(left[i], right[i])
        if max < g {
            max = g
        }
    }

    fmt.Println(max)
}

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

こうすることである整数を除いて最大公約数を求める処理は、その数の左側の整数群の最大公約数と右側の整数群の最大公約数の最小公約数を求めれば良い。

このように最小公約数の計算は計算順序などは問われないので計算順序も柔軟に変えて計算できる。

最小公倍数を求める問題

以下の最小公倍数を求める問題を考えてみる。

atcoder.jp

3つ以上の値の最小公倍数を求める問題。

単純に2つの値の最小公倍数を求める際は先ほど説明したa × b = g × lを使って求めることができる。

3つ以上の値の最小公倍数は1と1 つ目の値 の最小公倍数, 1と1つ目の値の最小公倍数と2つ目の値, ...という風に初めに1を使って求めていく。

コードで表現すると以下のようになる。

package main

import (
    "fmt"
)

func main() {
    var N int
    fmt.Scan(&N)
    T := make([]int, N)
    for i := 0; i < N; i++ {
        fmt.Scan(&T[i])
    }

    ans := 1
    for i := 0; i < N; i++ {
        ans = ans / GCD(ans, T[i]) * T[i]
    }

    fmt.Println(ans)
}

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

このようにユークリッドの互除法とa × b = g × lの性質を使って最大公約数と最小公倍数関連の問題は解いていく。