Q06 長方形から作る正方形

PHPのソース

<?php

//作成される正方形の数を返す
function DeriveSquareCnt($pX,$pY){
    if($pX > $pY){
        $Save = $pX;
        $pX = $pY;
        $pY = $Save;
    }
    if($pX === $pY) return 1;

    $ModVal = $pY % $pX;

    if ($ModVal === 0) return $pY / $pX;
    return ($pY - $ModVal) / $pX + DeriveSquareCnt($pX , $ModVal);
}

function Solve($pMaxLen,$NeedSquareCnt){
    $AnsweCnt = 0;
    for($X = 1 ; $X <= $pMaxLen ; $X++){
        for($Y = $X ; $Y <= $pMaxLen ; $Y++){
            $CurrSquareCnt = DeriveSquareCnt($X,$Y);
            if ($CurrSquareCnt !== $NeedSquareCnt) continue;

            //echo "横{$X},縦{$Y}での正方形は、{$CurrSquareCnt}個";
            //echo PHP_EOL;
            $AnsweCnt++;
        }
    }
    echo "最大長さ{$pMaxLen}での解は、{$AnsweCnt}通り";
    echo PHP_EOL;
}
Solve(   8, 5);
Solve(1000,20);

実行結果

最大長さ8での解は、8通り
最大長さ1000での解は、26882通り

解説

メモ化したら遅くなったので、メモ化しないようにしました。