Published

22/04/2026

Modified

22/04/2026

Matemática: Teoria dos Números

Metáfora e Motivação

Quando você e seus amigos juntam cards repetidos e querem distribuí-los em “pacotinhos perfeitos” de trocas idênticas sem sobrar nada, vocês estão, essencialmente, calculando o Máximo Divisor Comum (MDC).

A Teoria dos Números na programação competitiva destila problemas abstratos em engrenagens puras (como crivos e modularidade), transformando cálculos absurdos em operações ágeis.

Introdução Teórica

  1. Números Primos: Um número \(P > 1\) é primo se seus únicos divisores são 1 e \(P\).
    • Teste de Primalidade Isolada: Não precisamos iterar até \(N\). Basta varrer até a \(\sqrt{N}\). Todo fator maior que a raiz tem um par correlato perfeitamente espelhado menor que ela.
  2. Crivo de Eratóstenes: A estratégia bélica suprema para descobrir todos os primos até um limite massivo (ex: \(10^6\)).
    • Iteramos e marcamos os “múltiplos” (ex: riscamos 4, 6, 8, 10… cortamos 9, 15, 21…) como falsos. O que restar invicto é primo! Complexidade absurda: \(\mathcal{O}(N \log \log N)\).
  3. Aritmética Modular: Impede que o “Integer Overflow” mate sua linguagem ao armazenar fatoriações monstras. Lidamos ciclicamente pelo módulo (comumente \(10^9+7\)).
    • \((A + B) \% M = ((A \% M) + (B \% M)) \% M\)
    • \((A \times B) \% M = ((A \% M) \times (B \% M)) \% M\)

Algoritmo Euclidiano para MDC e MMC

Inventado antes de Cristo, a recursão mais bela da humanidade. O \(GCD(A, B)\) (Greatest Common Divisor) pode ser achado trocando \(A\) por \(B\), e \(B\) pelo resto de \(A / B\).

Abaixo, a simulação do Euclides caçando o MDC de 48 e 18:

Fórmula extra: O Mínimo Múltiplo Comum (MMC) é parente direto e grátis: \[MMC(A, B) = \frac{A \times B}{MDC(A, B)}\]

Implementações Oficiais na C++

#include <iostream>
#include <vector>
#include <numeric> // no c++17 em diante contem std::gcd!
#include <cassert>

using namespace std;

// 1. O Algoritmo milenar de Euclides na mao
int euclides_mdc(int a, int b) {
    if (b == 0) return a;
    return euclides_mdc(b, a % b);
}

// 2. Extensao direta para formacao do MMC
int mmc(int a, int b) {
    // Dividimos antes de multiplicar para evitar overflow em numeros grandes!
    return a / euclides_mdc(a, b) * b;
}

// 3. Crivo de Eratostenes (Retorna um vetor de booleanos onde v[i] = é_primo?)
vector<bool> crivo(int limite) {
    vector<bool> primo(limite + 1, true);
    primo[0] = false;
    primo[1] = false;
    
    for (int p = 2; p * p <= limite; p++) {
        if (primo[p] == true) {
            // Riscamos os mutiplos partindo do quadrado de 'p' 
            // (pois os menores ja foram riscados por primos menores q ele!)
            for (int i = p * p; i <= limite; i += p) {
                primo[i] = false;
            }
        }
    }
    return primo;
}

void executando_testes() {
    // A) Teste do Diagrama (48 e 18)
    assert(euclides_mdc(48, 18) == 6);
    
    // B) Teste do MMC (MMC de 4 e 6 é 12)
    assert(mmc(4, 6) == 12);
    
    // C) Teste do Crivo para numeros ate 30
    vector<bool> validador = crivo(30);
    assert(validador[2] == true);
    assert(validador[3] == true);
    assert(validador[4] == false);
    assert(validador[17] == true);
    assert(validador[27] == false); // 3x9
    assert(validador[29] == true);
    
    cout << "[✅] Testes Milenares (Crivo e Euclides) passaram limpos!\n";
}

int main() {
    executando_testes();
    return 0;
}

Exercício Guiado (Distribuindo Bens)

Problema: Beecrowd 1028 - Figurinhas

Raciocínio Adaptado: Ricardo e Vicente querem dividir suas pilhas colossais em sub-pilhas perfeitas, padronizadas com exatamente a mesma estatura sem quebrar ou descartar cards. “Pilhas em comum”. O maior tamanho dessa sub-pilha deve satisfazer as duas mãos, logo, nada mais é que um MDC(CartasRicardo, CartasVicente). Em submissões que ultrapassem milhões, não utilize For Loops! O euclides_mdc fará em 3 saltos.

Prática Avançada de Maratona (Teoria dos Números)

Back to top