php - Amazon InterviewStreet 斐波那契因子 - PHP

Question

我无法解决 php 中斐波那契因子的 Amazon Interviewstreet 挑战。 https://amazon.interviewstreet.com/challenges/dashboard/#problems

斐波那契值高达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);
}
?>

Answer 1

<?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;
}
?>

Answer 2

我没有尝试调试您的代码，但我编写了自己的解决方案......可能有效

<?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;
}