Language: C C++ D Haskell Lua OCaml PHP Perl Plain Text Python Ruby Scheme Tcl ; chinese remainder theorem (define (euclid x y) (let loop ((a 1) (b 0) (g x) (u 0) (v 1) (w y)) (if (zero? w) (values a b g) (let ((q (quotient g w))) (loop u v w (- a (* q u)) (- b (* q v)) (- g (* q w))))))) (define (inverse x m) (if (not (= (gcd x m) 1)) (error 'inverse "divisor must be coprime to modulus") (call-with-values (lambda () (euclid x m)) (lambda (a b g) (modulo a m))))) (define (chinese-remainder as ms) (let ((p (apply * ms))) (define (f a m) (let* ((t (/ p m)) (b (inverse t m))) (* a b t))) (modulo (apply + (map f as ms)) p))) (display (chinese-remainder '(2 3 2) '(3 5 7))) (newline) Private [?] Run code Submit