Matemática: Teoria dos Números

Metáfora e Motivação

Quando dois jogadores trocam figurinhas repetidas e querem saber quantos pacotinhos iguais podem formar, estão, na prática, calculando o MDC entre as quantidades de figurinhas de cada um. Esse tipo de situação aparece em muitos problemas de maratona.

Introdução Teórica

A Teoria dos Números em programação competitiva foca em propriedades dos números inteiros para resolver problemas de contagem, divisibilidade e criptografia básica de forma eficiente.

Conceitos Chave

  1. Números Primos: Um número \(P > 1\) é primo se seus únicos divisores são 1 e \(P\).
    • Teste de Primalidade: Basta verificar divisores até \(\sqrt{N}\). Complexidade \(O(\sqrt{N})\).
  2. Crivo de Eratóstenes: Algoritmo para gerar todos os primos até um limite \(N\).
    • Marcamos múltiplos de cada primo encontrado. Complexidade \(O(N \log \log N)\) (quase linear).
  3. MDC (Máximo Divisor Comum): O algoritmo de Euclides permite calcular \(GCD(A, B)\) em \(O(\log(\min(A, B)))\).
    • Propriedade: \(MMC(A, B) = (A \times B) / MDC(A, B)\).
  4. Aritmética Modular: Lidar com números muito grandes mantendo apenas o resto da divisão por \(M\) (geralmente \(10^9+7\)).
    • \((A + B) \% M = ((A \% M) + (B \% M)) \% M\)
    • \((A \times B) \% M = ((A \% M) \times (B \% M)) \% M\)

Implementações em Código

C++ (MDC com Algoritmo de Euclides)

int mdc(int a, int b) {
    return b == 0 ? a : mdc(b, a % b);
}

Java (MDC com Algoritmo de Euclides)

public static int mdc(int a, int b) {
    if (b == 0) {
        return a;
    }
    return mdc(b, a % b);
}

Python (MDC com Algoritmo de Euclides)

def mdc(a: int, b: int) -> int:
    while b != 0:
        a, b = b, a % b
    return a

Problema Clássico

Problema: Figurinhas (MDC) Link: Beecrowd 1028

Descrição: Dois jogadores trocam figurinhas repetidas. O “tamanho da pilha” de troca máxima comum é o Máximo Divisor Comum entre as quantidades de cada um. O problema pede simplesmente o MDC de vários pares de números.

Solução: Implementar o Algoritmo de Euclides Clássico ou usar std::gcd (C++17).

Exercício Prático Guiado

  1. Implemente o algoritmo de Euclides para o MDC em C++/Java/Python.
  2. Use-o para resolver o problema das figurinhas (Beecrowd 1028).
  3. Em seguida, adapte seu código para também calcular o MMC usando a relação \(MMC(A, B) = (A \times B) / MDC(A, B)\).

Variações e Exercícios

  1. [Primo Rápido]
    • Foco: Implementar o teste de primalidade \(O(\sqrt{N})\). O limite de tempo exige algo melhor que \(O(N)\).
    • Link: Beecrowd 1221
  2. [Macetes (Crivo)]
    • Foco: Problemas que exigem pré-calcular primos para responder múltiplas consultas rapidamente.
    • Link: Beecrowd 2674 (Super Primos: Primo e digitos primos).
  3. [Fatorial de Novo!]
    • Foco: Manipulação de strings grandes ou propriedades de divisibilidade do fatorial.
    • Link: Beecrowd 1429 (Conversão de base fatorial - Curiosidade Numérica).
Back to top