paizaの練習問題を解く最大公約数 Go編

こんにちは、ナナオです。

前回に引き続き競プロを実施していきたいと思います。

今回の問題は以下です。

最大公約数 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】

実装

まずは愚直に以下のように実装しました。

package main
import "fmt"
func main(){
    var a, b int
    fmt.Scan(&a, &b)
    min := 0
    if a < b {
        min = a
    } else {
        min = b
    }
    for i := min; i > 0; i++ {
        if a % i == 0 && b % i == 0 {
            fmt.Println(i)
            return
        }
    }
}

ですが、これだとタイムオーバーになってしまいました。

ということで修正します。

ユークリッドの互除法を用います。これは「AとBの最大公約数は、BとA%Bの公約数と等しい」という性質を利用して最大公約数を求める方法です。この方法を用いると計算量がO(log(max(A, B)))となります。

ユークリッドの互除法は再帰を使って簡単に実装できます。

package main
import "fmt"
func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}
func main(){
    var a, b int
    fmt.Scan(&a, &b)
    fmt.Println(gcd(a, b))
}

うーん、びっくりするくらい簡単に実装できましたね。。

ただすぐわすれちゃいそう…

というわけで今回はこれで👍

実装#

実装