我无法解决php中fibonacci因子的Amazon Interviewstreet挑战。https://amazon.interviewstreet.com/challenges/dashboard/#problems
Fibonacci值高达10^18
大的int值似乎是个问题，bcmath也于事无补。。。
我的代码-
<?php
function s($k)
{
$x=$y=1;
while($y<=$k)
{
$z=$x+$y;
$x=$y;
$y=$z;
if($y%2==0&&$k%2==0)
{
fprintf(fopen("php://stdout", "w"), "%d ", 2);
fprintf(fopen("php://stdout", "w"), "%d'n", 2);
return;
}
for($i=3;$i<=$y;$i+=2)
if($y%$i==0&&$k%$i==0)
{
fprintf(fopen("php://stdout", "w"), "%d ", $y);
fprintf(fopen("php://stdout", "w"), "%d'n", $i);
return;
}
}
while($y%$k!=0)
{
$z=$x+$y;
$x=$y;
$y=$z;
}
fprintf(fopen("php://stdout", "w"), "%d ", $y);
fprintf(fopen("php://stdout", "w"), "%d'n", $k);
}
fscanf(STDIN, "%d'n", $t);
while($t--)
{
fscanf(STDIN, "%d'n", $k);
s($k);
}
?>
我没有尝试调试您的代码，但我编写了自己的解决方案。。。可能工作
<?php
function findCommonFactor($input){
$x = 1;
$y = 2;
//check if the number is even
if($input % 2 == 0)
return 2;
$inputDivisor = findDivisor($input);
for($z = ($x+$y); $z <= $input; $z = ($x+$y)){
$x = $y;
$y = $z;
$fibonaciDivisor = findDivisor($z);
$commonDivisor = array_intersect($inputDivisor, $fibonaciDivisor);
if(count($commonDivisor)>0){
sort($commonDivisor);
return $z.' '.$commonDivisor[0];
}
}
return 'does not share any common factor';
}
function findDivisor($input){
// other than 1 and 2
$divisor = array();
for($i = 3; $i <= $input; $i = $i + 2){
if($input%$i == 0)
$divisor[] = $i;
}
return $divisor;
}
foreach(array(3, 5, 161) AS $val){
echo 'Input '.$val.' output '.findCommonFactor($val).PHP_EOL;
}
<?php
function s($k)
{
$e=1;$f=2;
while($f<=$k)
{
$g=$e+$f;
$e=$f;
$f=$g;
for($d=3;$d<=$f;$d+=2)
if($f%$d==0&&$k%$d==0)
return $f.' '.$d;
}
while(bcmod($f,$k)!=0)
{
$g=bcadd($e,$f);
$e=$f;
$f=$g;
}
return $f.' '.$k;
}
fscanf(STDIN, "%d'n", $t);
while($t--)
{
fscanf(STDIN, "%d'n", $k);
if($k%2==0)
echo '2 2'.PHP_EOL;
else
echo s($k).PHP_EOL;
}
?>