プログラムの最大公約数(gcd)問題をユーグリットの互除法で解く方法

最大公約数を求める問題の解法について、解説したいと思います。
まずは、最大公約数の定義についておさらいします。

最大公約数とは

2つの整数x,yにおいて、x ÷ d,y ÷ dの余りがともに0になるdのうち最大のものを
x,yの最大公約数(great common divisor訳してgcd)と言います。

最大公約数の例

２つの整数を35,14とすると、
35の約数は(1,5,7,35)、14の約数は(1,2,7,14)
この2数の公約数(1,7)のうち最大のもの7が最大公約数になります。

最大公約数を求める例題

AIZU ONLINE JUDGEの問題を例として、最大公約数を求める問題を解いてみたいと思います。

２つの自然数 x, y を入力とし、それらの最大公約数を求めるプログラムを作成してください。

入力

x と y が１つの空白区切りで１行に与えられます。

出力

最大公約数を１行に出力してください。

単純な解法

gcd(x,y)
 n = (xとyの小さい方の数)
 for dがnから1まで
  if dがxとyの約数
   return true

この解法は、与えれれた2数x,yのうち小さな数をnとして、
dがnから1までの間で、xとyがともに約数となる数を調べるコードになります。
この単純な解法だと規定時間内にクリアすることができないので、
ユーグリットの互除法を利用して問題を解きます。

ユーグリットの互除法とは

ユーグリットの互除法とは、
$x \geq y$の時関数gcd(x,y)と関数gcd(y,xをyで割った余り)は正しい
という定理のことです。

この定理を使って最大公約数を効率的に求めることができます。

ユーグリットの互除法の使用例

35,14の2数を例として、
ユーグリットの互除法をかけてみたいと思います。

gcd(35,14)
= gcd(35,35 % 14) = gcd(35,7)
= gcd(7,35 % 7) = gcd(7,0) = 7

gcd(a,b)において、b = 0となった時のaが与えられたa,bの最大公約数になります。

ユーグリットの互除法の証明

ユーグリットの互除法が正しいことを、aとbの公約数とbとr(a % b)の公約数が
正しいことを利用して証明します。

まず、dをaとbの公約数とします。
dは自然数l,mを用いて、a = ld,b = mdと表せます。

a = bq + rにa = ldを代入して、
ld = bq + r -①

①にb = mdを代入して、
ld = mdq + r

rについてまとめると

r = d(l - mq)が得られます。

この式からdがrの約数だということがわかります。

また、dはa,bの公約数なので、dはbを割り切ります。
なので、dはrとbの公約数になります。

同様の方法で、d'がbとrの公約数だとすると、d'はaとbの公約数であることがわかります。

よって、aとbの公約数の集合とrとbの公約数の集合は正しく、最大公約数も同じになります。

ユーグリットの互除法の計算効率

例として、74と54にユーグリットの互除法を適応して、
計算効率をチェックしてみます。

74 = 74 % 54 + 20(r1)
54 = 54 % 20 + 14(r2)
20 = 20 % 14 + 6(r3)
14 = 14 % 6 + 2(r4)
6 = 6 % 2 + 0(r5)

ここで、ユーグリットを適応して、得られた列(r1...r5)がどのように減っていったのかを考えます。

a = bq + rとすると(0 < r < b)、$r < \frac{a}{2}$より
$r_{i + 2} = \frac{n}{2}$が成り立ちます。

これより、ユーグリットの互除法は多くとも$2log_{2}(b)$で完了するので、
O(log(b))と見積もることができます

ユーグリットの互除法の疑似アルゴリズム

ユーグリットの互除法の疑似アルゴリズムは以下のようになります。

gcd(x,y)
 if x < y
   x >= yとなるようにxとyを入れ替える

 while y > 0
  r = x % y
  x = y
  y = r

return x;

cによる最大公約数を求める問題の解法

疑似アルゴリズムのユーグリットの互除法をcに直しています。

#include <algorithm>
#include <stdio.h>
using namespace std;

int gcd(int x,int y){
    int r;
    if(x < y){
        // 入れ替え
        swap(x,y);
    }
    
    while(y > 0){
        r = x % y;
        x = y;
        y = r;
    }
    return x;
}

int main(){
    int x,y;
    scanf("%d %d",&x,&y);
    printf("%d\n",gcd(x,y));
    return 0;
}