ユークリッドの互除法について勉強する - どこにでもいるSEの備忘録

最近、こっそりatcoderに取り組んでたりします。正直、競技プログラミング自体あまり得意ではないのですが、計算量に関して考える訓練としてやっています。

ということで、今回は珍しくアルゴリズムに関する記事です。

参考にしている本はこちら。

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

作者:秋葉拓哉,岩田陽一,北川宜稔
発売日: 2012/01/28
メディア: Kindle版

有名な蟻本ってやつですね。これ一冊勉強するのはめちゃくちゃ大変なので、今回はその中でもユークリッドの互除法ってやつを勉強してみたいと思います。

ユークリッドの互除法 is なに？
例題を試しに解いてみる
変形した問題も見てみる
参考文献
感想

ユークリッドの互除法 is なに？

ユークリッドの互除法は、2つの自然数について最大公約数を求めるための手法です。

ja.wikipedia.org

まず、シンプルに最大公約数を求めようとすると、

Aの約数A'を列挙
Bの約数B'を列挙
max(A'∩B')

といった流れになるかと思います。ただし、これだとA,Bが非常に大きな数字になった際に演算時間が非常に大きくなってしまいます。

これをユークリッドの互除法を使用すると効率的に計算することができます。

ユークリッドの互除法では、AとBの差でそれぞれを除算していきます。余りが0になったときの差が求める最大公約数になるという手法になります。この方法を使用すると、計算量としてははO(log n) になり、現実的な時間内で最大公約数を求めることができるようになります。

具体的にちょっと考えてみたいと思います。例として、A=32, B=20の最大公約数をユークリッドの互除法で求めます。

32を20で割った余りは12
20を12で割った余りは8
12を8で割った余りは4
8を4で割った余りは0

以上より、最大公約数は4というように求めることができます。なぜこれが成立するかの証明については、wikipediaを始め多く掲載されていますので、そちらをご参照ください。

ja.wikipedia.org

例題を試しに解いてみる

ここまでわかったところで、試しに実際の問題を解いてみたいと思います。

atcoder.jp

こちらの問題、各都市の座標 $x_i$ と初期値 $X$ を使用して、

$|x_i - X| = nD$

が成立すると、その都市にたどり着けることになるので、すべての $x_i$ に対して上式を満たすDの最大値を求める問題に読み替えることができます。ということで、この問題は最大公約数を求める問題に読み替えることができ、ユークリッドの互除法を使用することで高速に解くことができるわけです。

package main

import (
    "fmt"
)

func main(){
    var N, X, x int
    fmt.Scanf("%d %d",&N, &X)

    ans := 0
    for i:=0; i<N; i++{
        fmt.Scan(&x)
        if x > X{
            x = x-X
        }else{
            x = X-x
        }

        ans = gcd(ans, x)
    }

    fmt.Printf("%d\n", ans)
}

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

変形した問題も見てみる

ちょっとこちらの問題について見てみたいと思います。

atcoder.jp

一見すると最大公約数とは関係のない問題に見えます。

しかし、こちらに示されているように、実は下記の式が成立します。　

$gcd(x, y) = gcd(y, x-y)$

そのため、与えられた数字すべての最大公約数が、実は求める値になっているんですね。ということで、こんな感じに記述すると解くことができます。

package main

import (
  "fmt"
)

func main() {
  var N, a int
  fmt.Scan(&N)

  ans := 0
  for i := 0; i < N; i++ {
    fmt.Scan(&a)
    ans = gcd(ans ,a)
  }
  fmt.Printf("%d\n", ans)
}

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