【最大公約数】FINAL問題最大公約数 (paizaランク C 相当) 解答例 – PHP編【Aランクレベルアップメニュー】

【Aランクレベルアップメニュー】 > 【最大公約数】FINAL問題最大公約数 (paizaランク C 相当)
※リンク先へ移動する為には「paiza」へのログインが必要です。

本当にね…アルゴリズムね…無理だって(´；ω；`)
案の定自分では解けず、色々と調べてようやく通過。前回と同じく別言語のサンプルコードを何となく「PHP言語ならこうかな？」っとコードを書いてｒｙ。
テストケースには巨大な数値が設定されているので総当たりで公約数を調べることができません。今回の場合、「ユークリッドの互除法」というアルゴリズムを使います。
これは「AとBの最大公約数は、BとA%Bの公約数と等しい」という性質を利用して最大公約数を求める方法…らしいです。いや…分からん(;^ω^)

解答例

<?php
    $input = explode(" ",trim(fgets(STDIN)));
    $a = $input[0];
    $b = $input[1];
    function gcd($m, $n){ //ユークリッドの互除法
        if($n > $m) list($m, $n) = array($n, $m);
         
        while($n !== 0){
            $tmp_n = $n;
            $n = $m % $n;
            $m = $tmp_n;
        }
        return $m;
    }
    echo gcd($a , $b);
?>

<?php

$input = explode(" ",trim(fgets(STDIN)));

$a = $input[0];

$b = $input[1];

function gcd($m, $n){ //ユークリッドの互除法

if($n > $m) list($m, $n) = array($n, $m);

while($n !== 0){

$tmp_n = $n;

$n = $m % $n;

$m = $tmp_n;

}

return $m;

}

echo gcd($a , $b);

カテゴリー:paiza - レベルアップ問題集

タグ:Aランク Aランクレベルアップメニュー PHP paiza 問題集解答解答例

エッグ

エンジニアゲート

【最大公約数】FINAL問題最大公約数 (paizaランク C 相当) 解答例 – PHP編【Aランクレベルアップメニュー】

解答例

コメントを残すコメントをキャンセル

解答例

シェアする

関連投稿

【文字列の配列】STEP: 2 2 変数の入れ替え (paizaランク D 相当) – PHP編【配列メニュー】

【特殊な探索】STEP: 4 条件付き最大値 (paizaランク C 相当) 解答例 – PHP編【線形探索メニュー】

【0 が含まれていないか判定】STEP: 2 数値の分岐 (paizaランク D 相当) 解答例 – PHP編【条件分岐メニュー】

【指定された値の探索】STEP: 2 指定された値の位置 1 (paizaランク D 相当) 解答例 – PHP編【線形探索メニュー】

【文字列処理メニュー】部分文字列 (paizaランク D 相当) 解答例 – PHP編【paiza】

【へび】STEP: 5 幅のある移動 (paizaランク B 相当) 解答例 – PHP編【Aランクレベルアップメニュー】

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル