1234567891011121314151617181920212223 |
- #!/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);
|