Teoria dos Números

Escrito a partir da aula que o Fleischman me deu por GTalk (obrigada, Fleischman =D!), com edições do Lazera.

Notas de começo: onde temos contas (…) = (…) (mod x), leia congruente, em vez de igual.

Teorema de Bézout:

Definições:

a*x+b*y = gcd(a,b)
{a*x + b*y : x, y \in Z} = {k*gcd(a,b) : k \in Z}
O menor número positivo que pode ser escrito é gcd(a,b) (claramente pela observação acima)

Bézout e o inverso multiplicativo:

Quero calcular o inverso multiplicativo de a mod b – só existe se e somente se gcd(a,b)=1, pelo motivo que veremos daqui a pouco:
Inverso multiplicativo é x : (a*x) = 1 (mod b)

Então, por Bézout, temos: a*x+b*y = gcd(a,b) = 1
Aplicando %b dos dois lados, temos a*x = 1 (mod b), que é exatamente a definição de inverso multiplicativo.
Daí, podemos ver porque números não coprimos não têm inverso multiplicativo: quando tiramos o módulo, a*x = gcd(a,b), se gcd(a,b) != 1 não é possível chegar em a*x = 1 (mod b) para encontrar o inverso multiplicativo.

Calculando Bézout:

Calcular Bézout lembra muito o processo de calcular o gcd. Para quem não lembra, a recorrência do gcd é assim (em pseudo-código):

gcd(a,b) {
    se b==0, retorna a;
    c.c. retorna gcd(b,a%b);
}

Aplicando isso para Bézout, fica:
Se b==0, temos só a*x=gcd(a,0)=a, logo, podemos fazer x=1 e y=(qualquer coisa), tipicamente fazemos y=0; (dúvida aqui: funciona se eu colocar y=valor aleatório?) (Resposta do Fleischman: funciona (exceto por talvez overflow), mas sinceramente, pra que?)
Caso contrário, temos que a=b e b=a%b (pela recorrência acima), então fica:
b*x+(a%b)*y = gcd(a, b)
Podemos considerar a%b = a-(a/b)*b (definição de resto, onde a/b é uma divisão inteira), então, substituindo:
b*x+(a-(a/b)*b)*y = gcd(a, b)
Como x era a variável do coeficiente a e y a variável do coeficiente b, vamos rearrumar para obter quem são os novos x e y nessa conta:

a*(y)-b*(x-(a/b)*y)
x(novo) = y;
y(novo) = x-(a/b)*y;

Então, resumidamente, novamente em pseudo-código:

Se b==0, retorna (1,0);
c.c {
    Calcula x,y para extEuclid(b, a%b);
    retorna (y, x-(a/b)*y);
}

Aqui meu código em C++:
pair<int, int> extEuclid(int a, int b) {
    if (!b) return make_pair(1,0);

    pair<int,int> tmp = extEuclid(b,a%b);
    return make_pair(tmp.second, 
        tmp.first-(a/b)*tmp.second);
}

Complexidade: O(log(min(a,b))

Resolvendo congruências lineares usando Bézout:

Uma congruência linear é: a*x = b (mod n), onde a, b, n são dados. Congruências lineares têm solução se e somente se b é divisível por gcd(a,n) (por que não têm caso contrário?) (Fleischman: fica de excecício pro leitor :) )

(falta essa parte)

Um problema: http://br.spoj.pl/problems/MIOJO/

/* Spoilers zone*/
Isso é um esboço da minha solução, é possível que exista uma maneira bem mais esperta

A primeira observação a ser feita nesse problema é que queremos resolver uma equação do tipo A*x+B*y = T. Sabendo isso, podemos fazer duas congruências:
A*x = T (mod B)
B*y = T (mod A)

A segunda observação vem da interpretação de x e y para cada solução. Nas palavras do Fleischman:Daniel Fleischman
‘se x, y >= 0 isso da no mesmo que "espera A x vezes e B y vezes"…
os dois nao sao < 0 (pq T > 0)
entao, no caso de x >= 0 e y < 0 (s.p.d.g.), significa "comecando ao mesmo tempo, vire A x vezes e B y vezes… comece a cozinhar depois de acabarem todas as vezes de B, e acabe depois de acabarem todas as vezes de A" ’

Então, basicamente vemos se x,y>=0 – se forem, a resposta é a*x+b*y (Fleischman: que coincidentemente, é exatamente T :P). Caso contrário, a resposta é a*x, se x>=0, ou b*y, se y>=0

Usando a idéia em 1.3, podemos achar todas as soluções para cada uma dessas congruências e ver qual resulta no menor tempo.
/* End of spoilers zone */

Teorema de Euler:

Primeiro, uma definição:

phi(x) = | {1 <= k < x : (x, k) = 1} |, ou seja, phi(x) = quantidade de coprimos a x que são imenores que ele mesmo.
O teorema de Euler: se (a, N) = 1, então a^phi(N) = 1 (mod N)

Relação com o pequeno teorema de Fermat:

O pequeno teorema de Fermat: se p é primo e a é coprimo a p, a^(p-1) = 1 (mod p)
É fácil ver que, se p é primo, phi(p) = p-1, então podemos fazer a substituição:
a^(phi(p)) = 1 (mod p), que é exatamente o teorema de Euler. Ou seja, o Pequeno Teorema de Fermat é um caso especial do Teorema de Euler.

Para ser mais justo com Fermat, o certo seria dizer que o Teorema de Euler é uma generalização do Pequeno Teorema de Fermat, uma vez que Fermat é mais de 1 século mais velho que Euler.

Potência de números grandes tirando o módulo:

Muitos problemas da maratona pedem para que você opere com cálculos de números gigantes e retorne (N^p)%M, sendo M um número mais razoável. Por isso, existe esse "truque" para fazermos potência de um N muito grande, mantendo-o dentro de um range de M.

long long int M;

long long int potencia(long long int N, long long int p) {
     long long int res = 1;
     for(long long int i = 0 ; i<p ; i++)
          res = (res*N)%M;

     return res;
}

É algo bem simples e de grande utilidade. Precisou ser usado no problema I da Maratona desse ano (2014).

Crivo de Eratóstenes

Um método de fácil implementação e baixa complexidade para encontrar todos os primos até um limite N.

bool isPrime[N];
void crivo() {
        for (int i=0; i<N; i++)
                isPrime[i] = true;

        isPrime[0] = isPrime[1] = false;

        for (int p=2; p*p<N; p++) { // testa até a raiz quadrada de N
                while (!isPrime[p]) p++;

                for (int i=2; i*p<N; i++) // corta todos os múltiplos de p, que é primo
                        isPrime[i*p] = false;
        }
}

Simulação do problema de Josephus O(n^2)

O problema de Josephus é um clássico da matemática e da programação. Nele, existem N pessoas em círculo esperando para serem executadas, a contagem começa de um I qualquer do círculo e as pessoas são executadas em pulos de K em K. Ou seja, se temos N = 10, I = 2 e K = 3, a primeira pessoa a ser executada é a 5ª pessoa do círculo. A última pessoa viva recebe a liberdade e seu objetivo é descobrir que posição, dados N, I e K, ganhará a liberdade.

vector<int> r;

// r = {1, 2, 3, ... , N};

int josephus(int K, int I)
{
    int ini = I;

    int sz = r.size();
    while(sz > 1) {
                int prox = ((ini + (K-1))%sz); // K-1 porque nosso vetor é indexado de 0 (torna o problema mais fácil, inclusive)
        r.erase(r.begin() + prox); // erase(r[prox]);
        ini = (ini+(K-1))%sz;
        sz--;
    }

    return r[0];
}

Josephus com k=2 O(1)

Se observarmos a seguinte tabela podemos observar um padrão.

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
f(n) 1 1 3 1 3 5 7 1 3 5 7 9 11 13 15 1
  • Quando n é uma potência de 2, f(n) = 1.
  • Caso contrário, assumindo que n = 2^m + l, f(n) = 2*l +1. (Existe uma prova aqui)

Portanto, para o segundo caso, podemos descrever f(n) de uma forma geral da seguinte maneira:
f(n) = 2(n - 2^log(n))+1

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License