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
