MDC(252, 105):
  252 = 2 × 105 + 42    → MDC(252, 105) = MDC(105, 42)
  105 = 2 × 42 + 21     → MDC(105, 42)  = MDC(42, 21)
   42 = 2 × 21 + 0      → MDC(42, 21)   = MDC(21, 0)

  MDC(252, 105) = 21

Euclides Estendido — encontra x, y tal que ax + by = MDC(a, b):
  MDC(252, 105) = 21
  21 = 105 - 2×42
  42 = 252 - 2×105
  21 = 105 - 2×(252 - 2×105) = 5×105 - 2×252
  Então: 252×(-2) + 105×5 = 21 ✓

const std = @import("std");

/// MDC iterativo — O(log(min(a,b))).
pub fn mdc(a_param: u64, b_param: u64) u64 {
    var a = a_param;
    var b = b_param;
    while (b != 0) {
        const temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

/// MDC recursivo.
pub fn mdcRecursivo(a: u64, b: u64) u64 {
    if (b == 0) return a;
    return mdcRecursivo(b, a % b);
}

/// Mínimo Múltiplo Comum usando MDC.
pub fn mmc(a: u64, b: u64) u64 {
    if (a == 0 or b == 0) return 0;
    return (a / mdc(a, b)) * b; // evita overflow
}

/// Euclides Estendido — encontra x, y tal que ax + by = MDC(a, b).
pub fn mdcEstendido(a: i64, b: i64) struct { mdc_val: i64, x: i64, y: i64 } {
    if (a == 0) {
        return .{ .mdc_val = b, .x = 0, .y = 1 };
    }

    const resultado = mdcEstendido(@rem(b, a), a);
    return .{
        .mdc_val = resultado.mdc_val,
        .x = resultado.y - @divTrunc(b, a) * resultado.x,
        .y = resultado.x,
    };
}

/// Inverso modular usando Euclides Estendido.
/// Retorna x tal que (a * x) mod m = 1, ou null se não existir.
pub fn inversoModular(a: i64, m: i64) ?i64 {
    const resultado = mdcEstendido(a, m);
    if (resultado.mdc_val != 1) return null;
    return @mod(resultado.x, m);
}

/// MDC de múltiplos números.
pub fn mdcMultiplo(numeros: []const u64) u64 {
    if (numeros.len == 0) return 0;
    var resultado = numeros[0];
    for (numeros[1..]) |n| {
        resultado = mdc(resultado, n);
        if (resultado == 1) return 1;
    }
    return resultado;
}

/// MMC de múltiplos números.
pub fn mmcMultiplo(numeros: []const u64) u64 {
    if (numeros.len == 0) return 0;
    var resultado = numeros[0];
    for (numeros[1..]) |n| {
        resultado = mmc(resultado, n);
    }
    return resultado;
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();

    // MDC simples
    const pares = [_][2]u64{
        .{ 252, 105 },
        .{ 48, 18 },
        .{ 100, 75 },
        .{ 17, 13 },
    };

    try stdout.print("=== MDC e MMC ===\n", .{});
    for (pares) |par| {
        try stdout.print("MDC({d}, {d}) = {d}, MMC = {d}\n", .{
            par[0], par[1], mdc(par[0], par[1]), mmc(par[0], par[1]),
        });
    }

    // Euclides Estendido
    try stdout.print("\n=== Euclides Estendido ===\n", .{});
    const ext = mdcEstendido(252, 105);
    try stdout.print("252x + 105y = MDC → x={d}, y={d}, MDC={d}\n", .{ ext.x, ext.y, ext.mdc_val });
    try stdout.print("Verificação: 252×({d}) + 105×({d}) = {d}\n", .{
        ext.x, ext.y, 252 * ext.x + 105 * ext.y,
    });

    // Inverso modular
    try stdout.print("\n=== Inverso Modular ===\n", .{});
    if (inversoModular(3, 7)) |inv| {
        try stdout.print("Inverso de 3 mod 7 = {d} (3×{d} mod 7 = {d})\n", .{
            inv, inv, @mod(3 * inv, 7),
        });
    }

    // MDC de múltiplos números
    const nums = [_]u64{ 12, 18, 24, 36 };
    try stdout.print("\nMDC(12, 18, 24, 36) = {d}\n", .{mdcMultiplo(&nums)});
    try stdout.print("MMC(12, 18, 24, 36) = {d}\n", .{mmcMultiplo(&nums)});
}