Matemática: Teoria dos Números

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\)

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).

int mdc(int a, int b) {
    return b == 0 ? a : mdc(b, 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