fork download
copy 
  1. <?php // требует BCMath для арифметики длинных integer
  2.  
  3.     // Китайская теорема об остатках
  4.     //
  5.     // находит такое число res, что
  6.     // res = r (mod a)
  7.     // для всего массива (r, a)
  8.     //
  9.     // res = SUM r*m*mrev,
  10.     // где m = произведение всех a кроме очередного,
  11.     // mrev - обратный к m в Z/aZ
  12.  
  13.     // вход в виде
  14.     // (остаток, основание)
  15.     // основания должны быть попарно взаимно просты
  16.     // и остаток меньше основания
  17.     $data = [
  18.         [37,  1487],
  19.         [55,  1511],
  20.         [280, 1523],
  21.         [361, 1543],
  22.         [415, 1549],
  23.         [523, 1553],
  24.         [641, 1559]
  25.     ];
  26.  
  27.  
  28.     // сначала находим произведение Pa всех a
  29.     $Pa = 1; 
  30.     foreach ($data as list( ,$a)) $Pa = bcmul($Pa, $a);
  31.  
  32.     // заводим массив M слагаемых вида (r, m, mrev)
  33.     // где очередное m равно Pa/a
  34.     // то есть произведению всех a, кроме очередного
  35.     foreach ($data as list($r, $a)){
  36.         $m = bcdiv($Pa, $a);
  37.         $M[] = array($r, $m, getMr($m, $a));
  38.     } 
  39.  
  40.     // считаем res - сумму слагаемых из M
  41.     $res = 0;
  42.     foreach ($M as list($r, $m, $mrev))
  43.         $res = bcadd($res, bcmulClosure($r, $m, $mrev));   
  44.     echo $res;
  45.  
  46.  
  47.     // мультипликативно обратный к a в Z/bZ
  48.     function getMr($a, $b){
  49.         for ($i = 1; $i < $b; $i++)
  50.     	    if(bcmod(bcmul($a, $i), $b) == 1) return $i;
  51.     }
  52.  
  53.     // обобщение bcmul на несколько аргументов
  54.     function bcmulClosure(...$params){
  55.         $res = 1;
  56.         foreach($params as $v)$res = bcmul($res, $v);
  57.         return $res;
  58.     }
  59.  
  60. ?>
Runtime error #stdin #stdout #stderr 0s 82560KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
PHP Fatal error:  Uncaught Error: Call to undefined function bcmul() in /home/vqRTnz/prog.php:30
Stack trace:
#0 {main}
  thrown in /home/vqRTnz/prog.php on line 30
https://ideone.com/xaBwbR
language:
PHP (php 7.3.5)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!