Least Common Multiple

Q: Qual é a fórmula do MMC de dois números?

lcm(a, b) = a × b / gcd(a, b) , calculado como a / gcd(a, b) × b para que o valor intermediário nunca exceda a resposta. Para 4 e 6 , o mdc é 2 , e 4 / 2 × 6 = 12 .

Q: Qual é a complexidade de tempo para calcular o MMC?

Com a fórmula do mdc, a complexidade é O(log(min(a, b))) , o custo do algoritmo de Euclides, mais uma divisão e uma multiplicação. Ela precisa de O(1) de espaço extra. Procurar entre os múltiplos é muito mais lento: O(min(a, b)) quando você avança pelo número maior, e O(lcm(a, b)) quando conta de um em um.

Q: Como encontrar o MMC de mais de dois números?

Reduza a lista: lcm(a, b, c) = lcm(lcm(a, b), c) . Para [4, 6, 10] , lcm(4, 6) = 12 e lcm(12, 10) = 60 . O valor acumulado cresce rapidamente, então fique atento a estouros e use inteiros de 64 bits quando a lista for longa.

InicianteMatemática e simulação

+10

Você recebe dois números inteiros positivos a e b. Retorne o mínimo múltiplo comum: o menor número inteiro positivo que é divisível por a e b sem deixar resto.

Por exemplo, os múltiplos de 6 são 6, 12, 18, 24 e assim por diante; os múltiplos de 8 são 8, 16, 24 e assim por diante, e o primeiro número presente nas duas listas é 24.

Função

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

ainteger: o primeiro inteiro positivo
binteger: o segundo inteiro positivo
Retornainteger: o menor número inteiro positivo que é múltiplo tanto de a quanto de b

Restrições

1 ≤ a ≤ 10⁶
1 ≤ b ≤ 10⁶
A resposta cabe em um inteiro de 32 bits com sinal: lcm(a, b) ≤ 2³¹-1. O produto a × b talvez não.

Exemplos

Entrada: a = 4b = 6
Saída: 12
Explicação: Os múltiplos de 6 começam com 6, 12, 18; os múltiplos de 4 começam com 4, 8, 12. O primeiro número nas duas listas é 12.

Entrada: a = 7b = 3
Saída: 21
Explicação: 7 e 3 não têm nenhum fator em comum além de 1, então seu mínimo múltiplo comum é o produto deles, 21.

Entrada: a = 15b = 45
Saída: 45
Explicação: 15 divide 45 exatamente, então 45 já é um múltiplo de ambos, e não existe nenhum múltiplo menor de 45.

+15 testes ocultos ao enviar

Para ir além

Você consegue encontrar o mdc sem usar divisão nem resto, usando apenas subtração e divisão por 2?

Dicas

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

0 de 3 abertas

Solução

O mínimo múltiplo comum e o máximo divisor comum são dois lados de um mesmo fato: gcd(a, b) × lcm(a, b) = a × b. Portanto, a resposta rápida é a × b / gcd(a, b), com uma ressalva. O produto pode chegar a 10^12, o que causa estouro em um inteiro de 32 bits mesmo quando a resposta cabe, então você divide pelo MDC antes de multiplicar.

Conte a partir do número maior

Correta, mas não termina nos maiores testes

Intuição

A resposta é um múltiplo de ambos os números, então é pelo menos tão grande quanto o maior deles. Comece um candidato m em max(a, b) e some 1 até que tanto a quanto b o dividam. Você testa os candidatos em ordem crescente, então o primeiro que funciona é o menor.

Para 4 e 6, você testa 6, 7, 8, 9, 10 e 11, que não funcionam, e para em 12. O loop sempre termina, porque a × b é um múltiplo comum.

O número de tentativas é aproximadamente do tamanho da resposta. Para 46337 e 46327, dois números primos, a resposta é 2146654199, então o loop executa mais de dois bilhões de vezes. Isso é lento demais.

Algoritmo

Defina m como o maior entre a e b.
Enquanto m % a ou m % b não for 0, some 1 a m.
Retorne m.

def lcm(a, b):
    m = max(a, b)
    while m % a != 0 or m % b != 0:
        m += 1
    return m

Avance pelos múltiplos do número maior

Intuição

A maioria dos candidatos na contagem não serve: a resposta precisa ser um múltiplo do número maior, que vamos chamar de big. Então, pule direto de um múltiplo de big para o próximo: big, 2 × big, 3 × big, e pare no primeiro que seja divisível pelo número menor.

Para 4 e 6, você tenta 6 (4 não é divisível por ele) e depois 12 (é). A resposta é k × big para algum k, e k é no máximo o número menor, porque small × big é sempre um múltiplo comum. Portanto, o loop executa no máximo min(a, b) vezes, o que aqui nunca passa de um milhão.

Isso é rápido o suficiente aqui, mas ainda cresce com a entrada. Com números de até 10^18, não seria.

Algoritmo

Seja big o número maior e small o menor.
Defina m = big.
Enquanto m % small não for 0, adicione big a m.
Retorne m.

def lcm(a, b):
    big, small = max(a, b), min(a, b)
    m = big
    while m % small != 0:
        m += big
    return m

Divida pelo mdc e depois multiplique

Intuição

Decomponha ambos os números em fatores primos. O mdc usa cada primo com a menor de suas duas potências, o mmc usa a maior, e juntos eles usam cada fator de a e de b exatamente uma vez. Isso resulta em gcd(a, b) × lcm(a, b) = a × b, então lcm(a, b) = a × b / gcd(a, b). Para 4 = 2² e 6 = 2 × 3, o mdc é 2 e o mmc é 2² × 3 = 12.

Encontre o mdc usando o algoritmo de Euclides: substitua (x, y) por (y, x % y) até que y seja 0. Isso leva O(log(min(a, b))) etapas.

Depois, calcule a / gcd × b, nessa ordem. O mdc divide a exatamente, então a divisão não perde nada, e o resultado nunca excede a resposta. Escrever a × b / gcd em vez disso causa estouro de um inteiro de 32 bits para a = b = 10^6: o produto é 10^12, enquanto a resposta é apenas 10^6.

Algoritmo

Copie a e b para x e y.
Enquanto y não for 0, substitua (x, y) por (y, x % y). Agora, x é o gcd.
Divida a por x.
Multiplique o resultado por b e retorne-o.

def lcm(a, b):
    x, y = a, b
    while y != 0:
        x, y = y, x % y
    # x is gcd(a, b). Divide before multiplying.
    return a // x * b

Armadilhas e casos extremos

A fórmula está em uma linha, e os bugs estão na ordem das operações aritméticas.

Calcular a × b primeiro. Em Java, C, C++, C# e Rust, o produto de dois números próximos de 10^6 excede o limite de um inteiro de 32 bits, e a resposta sai errada ou negativa (em vez disso, uma compilação de depuração do Rust gera um panic), embora o lcm verdadeiro caiba.
Dividir a × b pelo mdc usando ponto flutuante. O resultado pode ser 2.146654199E9 ou perder seus últimos dígitos; mantenha tudo em números inteiros.
Executar o laço de Euclides com os próprios a e b e depois usá-los na fórmula. Após o laço, eles contêm o mdc e 0, então trabalhe com cópias.
Presumir que a resposta é a × b. Isso só vale quando os dois números não têm fatores em comum: lcm(4, 6) é 12, não 24.

Perguntas frequentes4

Qual é a fórmula do MMC de dois números?

lcm(a, b) = a × b / gcd(a, b), calculado como a / gcd(a, b) × b para que o valor intermediário nunca exceda a resposta. Para 4 e 6, o mdc é 2, e 4 / 2 × 6 = 12.

Por que gcd(a, b) × lcm(a, b) é igual a a × b?

Para cada número primo, o mdc usa o menor entre seus expoentes em a e b, e o mmc usa o maior. O menor mais o maior é a soma dos dois expoentes, que é exatamente o expoente desse número primo em a × b. Todos os números primos correspondem, então os dois produtos são iguais.

Qual é a complexidade de tempo para calcular o MMC?

Com a fórmula do mdc, a complexidade é O(log(min(a, b))), o custo do algoritmo de Euclides, mais uma divisão e uma multiplicação. Ela precisa de O(1) de espaço extra. Procurar entre os múltiplos é muito mais lento: O(min(a, b)) quando você avança pelo número maior, e O(lcm(a, b)) quando conta de um em um.

Como encontrar o MMC de mais de dois números?

Reduza a lista: lcm(a, b, c) = lcm(lcm(a, b), c). Para [4, 6, 10], lcm(4, 6) = 12 e lcm(12, 10) = 60. O valor acumulado cresce rapidamente, então fique atento a estouros e use inteiros de 64 bits quando a lista for longa.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

a = 4
b = 6

Esperado

Least Common Multiple

Função

Restrições

Exemplos

Dicas

Solução

Conte a partir do número maior

Avance pelos múltiplos do número maior

Divida pelo mdc e depois multiplique

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos