12345678910111213141516171819 |
- #!/usr/bin/ruby
- func invmod(a, n) {
- var (t, nt, r, nr) = (0, 1, n, a % n)
- while (nr != 0) {
- var quot = int((r - (r % nr)) / nr);
- (nt, t) = (t - quot*nt, nt);
- (nr, r) = (r - quot*nr, nr);
- }
- r > 1 && return()
- t < 0 && (t += n)
- t
- }
- var n = invmod(42, 2017)
- say n
- assert_eq(42.invmod(2017), n)
|