Greatest Common Divisor

Q: Qual é a complexidade de tempo do algoritmo de Euclides?

Ele é executado em O(log(min(a, b))) etapas, porque a cada duas etapas o número maior é reduzido pelo menos à metade. O pior caso é um par de números consecutivos de Fibonacci. Para números até 10^9 , isso corresponde a no máximo 43 etapas, e o algoritmo usa O(1) espaço extra.

Q: Por que gcd(a, b) é igual a gcd(b, a % b)?

Escreva a = q × b + r com r = a % b . Um número que divide a e b divide a - q × b , que é r . Um número que divide b e r divide q × b + r , que é a . Os dois pares têm os mesmos divisores comuns, então têm o mesmo maior divisor comum.

InicianteMatemática e simulação

+10

Você recebe dois números inteiros positivos a e b. Retorne o máximo divisor comum deles: o maior número inteiro que divide ambos sem deixar resto.

Por exemplo, os números que dividem tanto 8 quanto 12 são 1, 2 e 4, então a resposta é 4.

Função

gcd(a: integer, b: integer) → integer

ainteger: o primeiro número inteiro positivo
binteger: o segundo número inteiro positivo
Retornainteger: o maior inteiro que divide tanto a quanto b

Restrições

1 ≤ a ≤ 10⁹
1 ≤ b ≤ 10⁹

Exemplos

Entrada: a = 12b = 18
Saída: 6
Explicação: Os divisores de 12 são 1, 2, 3, 4, 6 e 12; os divisores de 18 são 1, 2, 3, 6, 9 e 18. O maior número que aparece nas duas listas é 6.

Entrada: a = 17b = 5
Saída: 1
Explicação: 17 e 5 são ambos primos e diferentes, portanto o único divisor que eles têm em comum é 1.

Entrada: a = 42b = 42
Saída: 42
Explicação: Um número divide a si mesmo, e nada maior que 42 pode dividir 42, então o máximo divisor comum de 42 e 42 é 42.

+14 testes ocultos ao enviar

Para ir além

Você consegue estender o algoritmo de Euclides para também retornar os inteiros x e y tais que a × x + b × y = gcd(a, b)?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

A definição sugere testar os candidatos um por um, e isso funciona com números pequenos. Porém, com a e b até 10^9, dois números grandes que não compartilham nenhum fator exigem um bilhão de tentativas. A observação de Euclides de que gcd(a, b) é igual a gcd(b, a % b) reduz os números tão rapidamente que nenhum par até 10^9 precisa de mais de 43 etapas.

Faça a contagem regressiva a partir do número menor

Correta, mas não termina nos maiores testes

Intuição

Nenhum divisor comum pode ser maior que o menor dos dois números, porque um divisor de b é no máximo b. Então, comece com um candidato d igual a min(a, b) e diminua-o de um em um até que ele divida ambos. Como você testa os candidatos de cima para baixo, o primeiro que funcionar é o maior.

Para 12 e 18, você testa 12 (ele não divide 18), depois 11, 10, 9, 8 e 7, que não funcionam, e para em 6. O loop sempre termina, porque 1 divide todos os números.

O custo é o número de candidatos. Para 999999937 e 999999929, que são primos, a resposta é 1 e o loop executa quase 10^9 vezes. Isso é lento demais para os maiores testes.

Algoritmo

Defina d como o menor entre a e b.
Enquanto a % d ou b % d não for 0, subtraia 1 de d.
Retorne d.

def gcd(a, b):
    d = min(a, b)
    while a % d != 0 or b % d != 0:
        d -= 1
    return d

Algoritmo de Euclides

Intuição

Escreva a = q × b + r, em que r = a % b. Qualquer número que divide tanto a quanto b também divide r = a - q × b. Qualquer número que divide tanto b quanto r também divide a = q × b + r. Portanto, os pares (a, b) e (b, r) têm exatamente os mesmos divisores comuns e o mesmo maior divisor.

Substitua (a, b) por (b, a % b) e repita até que b se torne 0. Todo número divide 0, então gcd(a, 0) = a, e a é a resposta. Para 12 e 18: (12, 18) se torna (18, 12), depois (12, 6), depois (6, 0), e a resposta é 6. A primeira etapa troca os números automaticamente quando a é menor, então você nunca precisa ordená-los.

A cada duas etapas, o maior número é reduzido pelo menos à metade, então o loop executa O(log(min(a, b))) vezes. As entradas mais lentas são números de Fibonacci consecutivos, como 701408733 e 433494437, e até mesmo elas levam apenas 42 etapas.

Algoritmo

Enquanto b não for 0, calcule r = a % b.
Defina a = b e b = r.
Quando b chegar a 0, retorne a.

def gcd(a, b):
    # gcd(a, b) == gcd(b, a % b), and gcd(a, 0) == a.
    while b != 0:
        a, b = b, a % b
    return a

Armadilhas e casos extremos

O algoritmo é curto, então os bugs vêm da atualização e da condição de parada.

Atualizar na ordem errada. a = b seguido de b = a % b calcula b % b, que é sempre 0, e retorna b. Primeiro, salve o resto em uma variável temporária ou atribua os dois valores de uma só vez.
Retornar b em vez de a quando o loop termina. Nesse ponto, b é 0.
Parar a contagem regressiva em 2 ou iniciá-la em max(a, b). A primeira opção deixa de considerar pares coprimos como 17 e 5; a segunda desperdiça tempo com candidatos que não podem dividir o menor número.
Usar subtrações repetidas em vez do resto. gcd(10^9, 1) então exige um bilhão de subtrações; % faz tudo isso em uma única etapa.

Perguntas frequentes4

Qual é a complexidade de tempo do algoritmo de Euclides?

Ele é executado em O(log(min(a, b))) etapas, porque a cada duas etapas o número maior é reduzido pelo menos à metade. O pior caso é um par de números consecutivos de Fibonacci. Para números até 10^9, isso corresponde a no máximo 43 etapas, e o algoritmo usa O(1) espaço extra.

Por que gcd(a, b) é igual a gcd(b, a % b)?

Escreva a = q × b + r com r = a % b. Um número que divide a e b divide a - q × b, que é r. Um número que divide b e r divide q × b + r, que é a. Os dois pares têm os mesmos divisores comuns, então têm o mesmo maior divisor comum.

Qual é a diferença entre MDC e MMC?

O máximo divisor comum é o maior número que divide ambos os valores de entrada; o mínimo múltiplo comum é o menor número que ambos os valores de entrada dividem. Eles estão relacionados por gcd(a, b) × lcm(a, b) = a × b; portanto, depois de obter o gcd, o lcm é a / gcd(a, b) × b.

Qual é o MDC de dois números coprimos?

Dois números são coprimos quando seu máximo divisor comum é 1, o que significa que eles não compartilham nenhum fator primo. Dois números primos diferentes são sempre coprimos, assim como quaisquer dois números inteiros consecutivos, como 8 e 9.

Python

def gcd(a, b):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

a = 12
b = 18

Esperado