sidef/scripts/chinese_remainder_theorem.sf

#!/usr/bin/ruby

func mul_inv(a, b) {
    b == 1 && return 1;
    var (b0, x0, x1) = (0, 0, 1);
    while (a > 1) {
        (a, b, x0, x1) = (b, a % b, x1 - x0*int(a / b), x0);
    };
    x1 < 0 ? x1+b0 : x1;
}

func chinese_remainder(*n) {
    var N = n«*»;
    func (*a) {
        n.range.map { |i|
            var p = int(N / n[i]);
            a[i] * mul_inv(p, n[i]) * p;
        }.sum
    }
}

say chinese_remainder(3, 5, 7)(2, 3, 2);