a^13 = a^(1101₂) = a^8 × a^4 × a^1

Em vez de 13 multiplicações → apenas 4 (3 ao quadrado + 1 multiplicação extra)

Calcular 3^13:
  13 em binário = 1101

  Iteração 1: bit=1 → resultado *= 3  → resultado=3,    base=3²=9
  Iteração 2: bit=0 → nada             → resultado=3,    base=9²=81
  Iteração 3: bit=1 → resultado *= 81 → resultado=243,  base=81²=6561
  Iteração 4: bit=1 → resultado *= 6561→ resultado=1594323

  3^13 = 1594323 ✓

Calcular 2^10 mod 1000:
  resultado=1, base=2
  bit=0: base=4
  bit=1: resultado=4, base=16
  bit=0: base=256
  bit=1: resultado=1024 mod 1000 = 24

  2^10 mod 1000 = 24 ✓

const std = @import("std");

/// Exponenciação rápida — calcula base^exp em O(log exp).
pub fn potencia(base_param: u64, exp_param: u64) u64 {
    var resultado: u64 = 1;
    var base = base_param;
    var exp = exp_param;

    while (exp > 0) {
        if (exp & 1 == 1) {
            resultado *= base;
        }
        base *= base;
        exp >>= 1;
    }
    return resultado;
}

/// Exponenciação modular — calcula (base^exp) mod m em O(log exp).
pub fn potenciaMod(base_param: u64, exp_param: u64, m: u64) u64 {
    if (m == 1) return 0;

    var resultado: u64 = 1;
    var base = base_param % m;
    var exp = exp_param;

    while (exp > 0) {
        if (exp & 1 == 1) {
            resultado = mulMod(resultado, base, m);
        }
        base = mulMod(base, base, m);
        exp >>= 1;
    }
    return resultado;
}

/// Multiplicação modular segura (evita overflow).
fn mulMod(a: u64, b: u64, m: u64) u64 {
    return @intCast(@as(u128, a) * @as(u128, b) % @as(u128, m));
}

/// Multiplicação de matrizes 2x2 (para Fibonacci, etc.).
const Mat2x2 = [2][2]u64;

fn matMul(a: Mat2x2, b: Mat2x2, m: u64) Mat2x2 {
    var resultado: Mat2x2 = undefined;
    for (0..2) |i| {
        for (0..2) |j| {
            var soma: u128 = 0;
            for (0..2) |k| {
                soma += @as(u128, a[i][k]) * @as(u128, b[k][j]);
            }
            resultado[i][j] = @intCast(soma % @as(u128, m));
        }
    }
    return resultado;
}

/// Exponenciação de matriz 2x2 — O(log n).
pub fn matPow(mat: Mat2x2, exp_param: u64, m: u64) Mat2x2 {
    var resultado: Mat2x2 = .{ .{ 1, 0 }, .{ 0, 1 } }; // identidade
    var base = mat;
    var exp = exp_param;

    while (exp > 0) {
        if (exp & 1 == 1) {
            resultado = matMul(resultado, base, m);
        }
        base = matMul(base, base, m);
        exp >>= 1;
    }
    return resultado;
}

/// Teste de primalidade de Miller-Rabin (usa exponenciação modular).
pub fn ehPrimo(n: u64) bool {
    if (n < 2) return false;
    if (n < 4) return true;
    if (n % 2 == 0 or n % 3 == 0) return false;

    // Escreve n-1 = d * 2^r
    var d = n - 1;
    var r: u32 = 0;
    while (d % 2 == 0) {
        d /= 2;
        r += 1;
    }

    // Testa com bases determinísticas para n < 3.317.044.064.679.887.385.961.981
    const testemunhas = [_]u64{ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };
    for (testemunhas) |a| {
        if (a >= n) continue;
        var x = potenciaMod(a, d, n);
        if (x == 1 or x == n - 1) continue;

        var encontrou = false;
        for (0..r - 1) |_| {
            x = mulMod(x, x, n);
            if (x == n - 1) {
                encontrou = true;
                break;
            }
        }
        if (!encontrou) return false;
    }
    return true;
}

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

    // Exponenciação simples
    try stdout.print("=== Exponenciação Rápida ===\n", .{});
    try stdout.print("2^10 = {d}\n", .{potencia(2, 10)});
    try stdout.print("3^13 = {d}\n", .{potencia(3, 13)});

    // Exponenciação modular
    try stdout.print("\n=== Exponenciação Modular ===\n", .{});
    try stdout.print("2^10 mod 1000 = {d}\n", .{potenciaMod(2, 10, 1000)});
    try stdout.print("7^256 mod 13 = {d}\n", .{potenciaMod(7, 256, 13)});
    try stdout.print("2^1000000 mod 1000000007 = {d}\n", .{potenciaMod(2, 1_000_000, 1_000_000_007)});

    // Teste de primalidade
    try stdout.print("\n=== Miller-Rabin (usa exp. modular) ===\n", .{});
    const testes = [_]u64{ 2, 17, 100, 997, 1000000007 };
    for (testes) |n| {
        try stdout.print("{d} é primo? {}\n", .{ n, ehPrimo(n) });
    }

    // Fibonacci com exponenciação de matriz
    try stdout.print("\n=== Fibonacci via Matriz ===\n", .{});
    const fib_mat: Mat2x2 = .{ .{ 1, 1 }, .{ 1, 0 } };
    const m: u64 = 1_000_000_007;
    for ([_]u64{ 10, 50, 100 }) |n| {
        const resultado = matPow(fib_mat, n, m);
        try stdout.print("F({d}) mod 10^9+7 = {d}\n", .{ n, resultado[0][1] });
    }
}