36 lines
1 KiB
Text
36 lines
1 KiB
Text
mul_inv = proc (a, b: int) returns (int) signals (no_inverse)
|
|
if b<0 then b := -b end
|
|
if a<0 then a := b - (-a // b) end
|
|
t: int := 0
|
|
nt: int := 1
|
|
r: int := b
|
|
nr: int := a // b
|
|
while nr ~= 0 do
|
|
q: int := r / nr
|
|
t, nt := nt, t - q*nt
|
|
r, nr := nr, r - q*nr
|
|
end
|
|
if r>1 then signal no_inverse end
|
|
if t<0 then t := t+b end
|
|
return(t)
|
|
end mul_inv
|
|
|
|
start_up = proc ()
|
|
pair = struct[a, b: int]
|
|
tests: sequence[pair] := sequence[pair]$
|
|
[pair${a: 42, b: 2017},
|
|
pair${a: 40, b: 1},
|
|
pair${a: 52, b: -217},
|
|
pair${a: -486, b: 217},
|
|
pair${a: 40, b: 2018}]
|
|
|
|
po: stream := stream$primary_output()
|
|
for test: pair in sequence[pair]$elements(tests) do
|
|
stream$puts(po, int$unparse(test.a) || ", "
|
|
|| int$unparse(test.b) || " -> ")
|
|
stream$putl(po, int$unparse(mul_inv(test.a, test.b)))
|
|
except when no_inverse:
|
|
stream$putl(po, "no modular inverse")
|
|
end
|
|
end
|
|
end start_up
|