【ユークリッドの互除法メニュー】ユークリッドの互除法 (paizaランク C)-解答例-PHP編

2022年8月20日

【ユークリッドの互除法メニュー】> 【拡張ユークリッドの互除法】STEP: 1 ユークリッドの互除法 (paizaランク C 相当) [難易度: 1383 ±27]

※リンク先へ移動するためには[paiza]へのログインが必要です。

問題文

2 つの整数 A , B の最大公約数（以後 gcd(A , B)）を高速に求めるアルゴリズムとして、ユークリッドの互除法があります。
gcd(A, B) をユークリッドの互除法で求める手順は次の通りです。

1. A , B のうち、いずれかが 0 の場合手順 3 に進む
2. A , B のうち小さい方で大きい方をわり、大きい方をその余りで置き換え、手順 1 に戻る
3. このとき、0 でない方の数が求めたい最大公約数になっている。

例として A = 15 , B = 40 にユークリッドの互除法を用いて最大公約数を求めると、次の通りになります。
（[]内の数字は手順の番号を表す）

[2] A = 15 , B = 40
[3] A < B なので B / A = 2 余り 10 より B = 10
[2] A = 15 , B = 10
[3] B < A なので A / B = 1 余り 5 より A = 5
[2] A = 5 , B = 10
[3] A < B なので B / A = 2 余り 0 より B = 0
[2] A = 5 , B = 0
[4] よって、15 と 40 の最大公約数は 5 となる。

2 つの整数 A , B が与えられるので、ユークリッドの互除法を用いて A , B の最大公約数を求めましょう。

入力値（例）
45 15

出力値（例）
15

解答例

<?php
    list($a, $b) = explode(" ", trim(fgets(STDIN)));
    
    // 自然数 a > b を確認・入替
    if ($a < $b) {
        $tmp = $a;
        $a = $b;
        $b = $tmp;
    }
    
    // ユークリッドの互除法
    $r = $a % $b;
    while ($r != 0) {
        $a = $b;
        $b = $r;
        $r = $a % $b;
    }
    echo $b. "\n";
?>

<?php

list($a, $b) = explode(" ", trim(fgets(STDIN)));

// 自然数 a > b を確認・入替

if ($a < $b) {

$tmp = $a;

$a = $b;

$b = $tmp;

}

// ユークリッドの互除法

$r = $a % $b;

while ($r != 0) {

$a = $b;

$b = $r;

$r = $a % $b;

}

echo $b. "\n";

解答例

カテゴリー