Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM9, Matemática - Coggle Diagram
-
Matemática
-
-
-
-
-
Teoria dos Jogos
Definição e contexto
Modelagem de decisões estratégicas; foco em jogos de soma zero entre dois jogadores com jogadas alternadas e Perfect Play
-
-
velocidade em matemática
-
Reduzir espaço de estados por observações (estratégias dominantes, invariantes)
-
-
-
Fatoração
Dividir por tentativa: dividir por primos até √N; ser simples, funcionar```plaintext
-
- Identificar se o problema pedir valor exato, valor mod m, confirmação (ex.: ser primo), contagem ou apenas padrão.
- Preferir sempre algoritmos que reduzirem a entrada: trabalhar com expoentes de primos, manter tudo módulo m, usar combinatória recursiva ou programar dinamicamente quando possível.
- Evitar usar BigInteger se houver alternativa (modularizar, fatorar, aplicar fórmulas combinatórias). Usar BigInteger somente quando realmente necessário.
Aritmética modular
Calcular (a+b) mod m = (a mod m + b mod m) mod m, e similar para produto.
-
Para expoente grande (em base ou string): iterar dígito a dígito usando identidade a^{10x+y} = (a^{10x} * a^{y}).
Calcular inverso modular: a^{-1} mod m existir quando gcd(a,m)=1. Usar Euclides estendido ou Fermat se m for primo.
Aplicar teoremas úteis: Fermat, Euler, CRT (Teorema Chinês dos Restos).
Combinatória e binomiais
Usar fórmulas: C(n,k) = n! / (k! (n-k)!), recorrência de Pascal.
-
Usar teorema de Lucas para C(n,k) mod p com n,k grandes e p pequeno.
-
Calcular Catalan: Cat(n) = (1/(n+1)) * C(2n, n), recorrência Cat(0)=1, Cat(n+1)=Σ Cat(i)·Cat(n−i).
-
-
Fatorar
Dividir por tentativa: dividir por primos até √N; ser simples, funcionar para fatores pequenos, mas ser lento se N tiver fator primo grande.
Usar spf (crivo linear): se precisar fatorar muitos números ≤ N, pré-computar spf e fatorar cada número em O(log N).
Usar Pollard‑Rho para fatorar inteiros grandes, especialmente com fatores médios/grandes. Combinar crivo para fatores pequenos e Pollard‑Rho para restos grandes.
-
Fatorial, expoentes primos e aplicações
-
Para n grandes, trabalhar via fatores primos ou modularizar.
-
-
- Identificar se o problema pede valor exato, valor mod m, confirmação (ex.: ser primo?), contagem, ou apenas padrão.
- Preferir sempre algoritmos que reduzam a entrada: trabalhar com expoentes de primos, manter tudo módulo m, usar combinatória recursiva ou programação dinâmica quando possível.
- Evitar BigInteger se houver alternativa (modular, fatoração, fórmulas combinatórias). Usar BigInteger somente quando realmente necessário.