::SANKAI::

最近太閒，所看了韓信點兵的故事，其中有提到算兵數的問題，就試著去研究一下後寫了一個函式

/*********************
 * 使用範例
 * Demo
 *********************/
//測試資料1(Test Data1)
$data1 = array(
    '2' => 1,//除2餘1，數學式：x ≡ 1 (mod 2)
    '3' => 2,//除3餘2，數學式：x ≡ 2 (mod 3)
    '5' => 4,//除5餘4，數學式：x ≡ 4 (mod 5)
    '7' => 0 //除7餘0，數學式：x ≡ 0 (mod 7)
);
//測試資料2(Test Data2)
$data2 = array(
    '3' => 2,//除3餘2，數學式：x ≡ 2 (mod 3)
    '5' => 3,//除5餘3，數學式：x ≡ 3 (mod 5)
    '7' => 2 //除7餘2，數學式：x ≡ 2 (mod 7)
);
echo CRT($data1);//output 203
echo CRT($data2);//output 23

/***********************************************
 * 中國餘數定理
 * 注意：需要用到求得多數最小公倍數的函式
 * Chinese Remainder Theory
 * Note: require function LCM_NUMS()
 ************************************************/
function CRT($data){
    $sum = 0;
    foreach($data as $key => $val){
        if($val == 0){
            $p[] = $key;
            unset($data[$key]);
        }
    }
    foreach($data as $key => $val){
        $clone = $data;
        unset($clone[$key]);
        $lcm = LCM_NUMS(array_keys($clone));
        $i = 1;
        while($find%$key == 1) {
            $find = $lcm*$i;
            $i++;
        }
        $sum += $val*$lcm;
    }
    return $sum%array_product(array_keys($data))*LCM_NUMS($p);
}

/**********************************************************************************
 * 最小公倍數與最大公因數函式
 * 原始碼來源：
 * Least Common Divisor / Greatest Common Mulitple
 * Source: http://www.ideashower.com/our_solutions/leastgreatest-common-mulitple-lcmgcm-in-php-and-javascript/
 **********************************************************************************/
//求得兩數最大公因數(Greatest Common Divisor)
function GCD($a, $b) {
	return ( $b == 0 ) ? ($a):( GCM($b, $a % $b) );
}
//求得兩數最小公倍數(Least Common Mulitple)
function LCM($a, $b) {
	return ( $a / GCD($a,$b) ) * $b;
}
//求得多數最小公倍數(Least Common Mulitple For Array)
function LCM_NUMS($ar) {
    if (count($ar) > 1) {
	$ar[] = LCM( array_shift($ar) , array_shift($ar) );
	return LCM_NUMS( $ar );
    } else if(count($ar) == 1){
        return $ar[0];
    } else {
        return 1;
    }
}