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

2022年8月23日

【ユークリッドの互除法メニュー】> 【拡張ユークリッドの互除法】STEP: 3 最小公倍数 (paizaランク C 相当) [難易度: 1517 ±34]

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

問題文

最大公約数（以後 gcd）と対になる値として、最小公倍数（以後 lcm）があります。
一般的に直接 lcm を求めるよりも、gcd を求めてから計算によって lcm を求める方が簡単とされています。
2 つの整数 A , B の lcm(A,B) は、lcm(A,B) = A×B/gcd(A,B) で求めることができます。
2 つの整数 A , B が与えられるので、lcm (A,B) を求めてください。

入力値（例）
6 39

出力値（例）
78

解答例

<?php
    list($a, $b) = explode(" ", trim(fgets(STDIN)));
    
    //最大公約数
    function gcd($x, $y){
        if($y > $x) list($x, $y) = array($y, $x);
         
        while($y !== 0){
            $tmp = $y;
            $y = $x % $y;
            $x = $tmp;
        }
        return $x;
    }
     
    //最小公倍数
    function lcm($x, $y){
        return $x * $y / gcd($x, $y);
    }
    
    echo lcm($a, $b);
?>

<?php

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

//最大公約数

function gcd($x, $y){

if($y > $x) list($x, $y) = array($y, $x);

while($y !== 0){

$tmp = $y;

$y = $x % $y;

$x = $tmp;

}

return $x;

}

//最小公倍数

function lcm($x, $y){

return $x * $y / gcd($x, $y);

}

echo lcm($a, $b);

解答例

カテゴリー