30 lines
597 B
Zig
30 lines
597 B
Zig
const std = @import("std");
|
|
|
|
fn mod_inv(a: isize, module: isize) isize {
|
|
var mn_0 = module;
|
|
var mn_1 = a;
|
|
var xy_0: isize = 0;
|
|
var xy_1: isize = 1;
|
|
|
|
while (mn_1 != 0) {
|
|
const xy_0_temp = xy_1;
|
|
xy_1 = xy_0 - @divFloor(mn_0, mn_1) * xy_1;
|
|
xy_0 = xy_0_temp;
|
|
|
|
const mn_0_temp = mn_1;
|
|
mn_1 = @rem(mn_0, mn_1);
|
|
mn_0 = mn_0_temp;
|
|
}
|
|
|
|
while (xy_0 < 0) {
|
|
xy_0 += module;
|
|
}
|
|
|
|
return xy_0;
|
|
}
|
|
|
|
pub fn main() !void {
|
|
const stdout = std.io.getStdOut().writer();
|
|
try stdout.print("{d}\n", .{mod_inv(42, 2017)});
|
|
}
|