17 lines
368 B
Plaintext
17 lines
368 B
Plaintext
procedure main(args)
|
|
a := integer(args[1]) | 42
|
|
b := integer(args[2]) | 2017
|
|
write(mul_inv(a,b))
|
|
end
|
|
|
|
procedure mul_inv(a,b)
|
|
if b == 1 then return 1
|
|
(b0 := b, x0 := 0, x1 := 1)
|
|
while a > 1 do {
|
|
q := a/b
|
|
(t := b, b := a%b, a := t)
|
|
(t := x0, x0 := x1-q*x0, x1 := t)
|
|
}
|
|
return if (x1 > 0) then x1 else x1+b0
|
|
end
|