Project Euler にチャレンジ:Problem 66 PHPでの解答

← Problem 65  Problem 67 →
<?php

// 問64の応用で解けるらしい。
// 連分数をまずは求めて、
// 連分数が1つのときは、それを使用
// 連分数が2つ以上の時は、末尾のを削って使用
// また連分数が奇数の時は2乗する。

$max_answer = 0;
$answer = 0;

for($i = 1 ; $i <= 1000 ; $i++)
{
        $sqrt = sqrt($i);
        // 無理数か否かをチェック
        if($sqrt != (int)$sqrt)
        {

                $tmp_array = array();
                // bunbo の初期値
                $tmp1 = (int)$sqrt;
                $tmp2 = 1;
                $tmp1_0 = 0;
                $tmp2_0 = 0;
                while(true)
                {
                        $bunbo = ($i - $tmp1 * $tmp1) / $tmp2;
                        $bunshi = $tmp1;
                        $tmp3 = 0;
                        while($bunshi > $sqrt * -1)
                        {
                                $bunshi = $bunshi -  $bunbo;
                                $tmp3 ++;
                        }
                        $bunshi = $bunshi + $bunbo;
                        $tmp3 --;
                        $tmp_array[] = $tmp3;
                        $tmp1 = $bunshi * -1;
                        $tmp2 = $bunbo;
                        if(count($tmp_array) == 1)
                        {
                                // 最初に出てくる $tmp1 と $tmp2 を覚える
                                $tmp1_0 = $tmp1;
                                $tmp2_0 = $tmp2;
                        }
                        // $tmp1_0 と $tmp1 , $tmp2_0 と $tmp2 の値が一致したら循環したということで、
                        // ループ終了
                        else if($tmp1_0 == $tmp1 and $tmp2_0 == $tmp2)
                        {
                                break;
                        }
                }
		array_pop($tmp_array);
		
		$count = count($tmp_array);
		if($count >= 2)
		{
			array_pop($tmp_array);
                	$x = array((int)$sqrt,1 + $tmp_array[0] * (int)$sqrt);
                	$y = array(1,$tmp_array[0]);
			for($j = 1 ; $j < $count - 1; $j ++)
			{
				$x[] = $x[ $j ] * $tmp_array[$j ] + $x[$j - 1] ;
				$y[] = $y[ $j ] * $tmp_array[$j ] + $y[$j - 1] ;
			}
		}
		else
		{
			$x = array((int)($sqrt));
			$y = array(1);
		}
                if($count % 2 == 1)
                {
			$tmp_answer = end($x) * end($x) + $i * end($y) * end($y);
                }
		else
		{
			$tmp_answer = end($x);
		}
		
		if($max_answer < $tmp_answer)
		{
			$max_answer = $tmp_answer;			
			$answer = $i;
		}
        }
}
echo $answer;
問題文