【ユークリッドの互除法メニュー】3 つ以上の整数の最大公約数 (paizaランク C)-解答例-PHP編

2022年8月20日

【ユークリッドの互除法メニュー】> 【拡張ユークリッドの互除法】STEP: 2 3 つ以上の整数の最大公約数 (paizaランク C 相当) [難易度: 1661 ±30]

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

問題文

2 つの整数 A , B の最大公約数（以後 gcd(A , B))を高速に求めるアルゴリズムとして、ユークリッドの互除法があります。
gcd の演算では、3 つの整数 a, b, c の最大公約数は、gcd(gcd(a,b),c) で求めることができます。
これは 4 つ以上の整数の場合も同様に、a , b , c , d , e , ... の最大公約数は
gcd(...gcd(gcd(gcd(gcd(a,b),c),d),e)...) で求めることができます。

例として、(9,27,33) の最大公約数は gcd(gcd(9,27),33) = gcd(9,33) = 3 といった具合に求めることができます。

与えられる整数の数 N と、整数 A_1, ..., A_N が与えられるので、 A_1, ..., A_N の最大公約数を求めてください。

入力値（例）
3
6
18
30

出力値（例）
6

解答例

<?php
    $n = trim(fgets(STDIN));
    for ($i = 0; $i < $n; $i++) {
        $a[] = trim(fgets(STDIN));
    }
    
    $ans = $a[0];
    
    for ($i = 0; $i < $n-1; $i++) {
        $ans = gcd($ans, $a[$i+1]);
    }
    
    printf("%d\n", $ans);
    
    function gcd($x, $y) {
        if($x == 0) return $y;
        if($y == 0) return $x;
        
        if ($x > $y) {
            return gcd($x % $y, $y);
            
        } elseif ($y > $x) {
            return gcd($x, $y % $x);
        }
        
        return -1;
    }
?>

<?php

$n = trim(fgets(STDIN));

for ($i = 0; $i < $n; $i++) {

$a[] = trim(fgets(STDIN));

}

$ans = $a[0];

for ($i = 0; $i < $n-1; $i++) {

$ans = gcd($ans, $a[$i+1]);

}

printf("%d\n", $ans);

function gcd($x, $y) {

if($x == 0) return $y;

if($y == 0) return $x;

if ($x > $y) {

return gcd($x % $y, $y);

} elseif ($y > $x) {

return gcd($x, $y % $x);

}

return -1;

}

解答例

カテゴリー