Least Common Multiple
Você recebe dois números inteiros positivos a e b. Retorne o mínimo múltiplo comum deles: o menor número inteiro positivo que é divisível por a e b sem deixar resto.
Função
- ainteger
- o primeiro inteiro positivo
- binteger
- o segundo número inteiro positivo
- Retornainteger
- o menor inteiro positivo que é múltiplo de a e b
Restrições
1 ≤ a ≤ 1061 ≤ b ≤ 106- A resposta cabe em um inteiro com sinal de 32 bits:
lcm(a, b) ≤ 231-1. O produtoa × btalvez não.
Exemplos
- Entrada
- a = 4b = 6
- Saída
- 12
- Explicação
- Os múltiplos de
6começam com 6, 12, 18; os múltiplos de4começam com 4, 8, 12. O primeiro número em ambas as listas é12.
- Entrada
- a = 7b = 3
- Saída
- 21
- Explicação
7e3não compartilham nenhum fator além de1, então seu mínimo múltiplo comum é o produto deles,21.
- Entrada
- a = 15b = 45
- Saída
- 45
- Explicação
15divide45exatamente, então45já é um múltiplo de ambos, e não existe nenhum múltiplo menor de45.
Para ir além
Você consegue encontrar o MDC sem usar divisão nem resto, usando apenas subtração e divisão por dois?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
A resposta é um múltiplo do número maior. Você precisa testar todos os números entre eles ou apenas os múltiplos do maior?
O máximo divisor comum e o mínimo múltiplo comum estão relacionados:
gcd(a, b) × lcm(a, b) = a × b. O algoritmo de Euclides encontra o mdc em algumas dezenas de etapas.Calcule o mdc e, em seguida, retorne
a / gcd × b. Divida primeiro: o produtoa × bpode exceder o limite de um inteiro de 32 bits mesmo quando a resposta cabe nesse limite.
Solução
O mínimo múltiplo comum e o máximo divisor comum estão relacionados por um fato: gcd(a, b) × lcm(a, b) = a × b. Portanto, a resposta rápida é a × b / gcd(a, b). O produto pode chegar a 10^12 e exceder o limite de um inteiro de 32 bits, mesmo quando a resposta cabe, então divida pelo mdc antes de multiplicar.
Conte a partir do número maior
Correta, mas não termina nos maiores testes
Intuição
A resposta é pelo menos o maior número. Comece m em max(a, b) e some 1 até que ambos os números dividam esse valor; você testa candidatos em ordem crescente, então o primeiro que funcionar é o menor. Para 4 e 6, você testa de 6 a 11 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 os números primos 46337 e 46327, a resposta é 2146654199, mais de dois bilhões de tentativas.
Algoritmo
- Defina
mcomo o maior entreaeb. - Enquanto
m % aoum % bnão for0, adicione 1 am. - Retorne
m.
def lcm(a, b):
m = max(a, b)
while m % a != 0 or m % b != 0:
m += 1
return mAvance pelos múltiplos do número maior
Intuição
A resposta deve ser um múltiplo do número maior, big, então avance de big em big: big, 2 × big, 3 × big, e pare no primeiro valor divisível pelo número menor. Para 4 e 6, você tenta 6 e depois 12.
Como small × big é sempre um múltiplo comum, o loop executa no máximo min(a, b) vezes, no máximo um milhão neste caso. Isso é rápido o suficiente para esses limites, mas ainda cresce com a entrada; com números de até 10^18, não seria.
Algoritmo
- Seja
bigo número maior esmallo menor. - Defina
m = big. - Enquanto
m % smallnão for0, somebigam. - Retorne
m.
def lcm(a, b):
big, small = max(a, b), min(a, b)
m = big
while m % small != 0:
m += big
return mDivida pelo mdc e, em seguida, multiplique
Intuição
Divida ambos os números em fatores primos. Para cada primo, o mdc usa a menor de suas duas potências, e o mmc, a maior; assim, juntos, eles usam cada fator de a e de b exatamente uma vez: gcd × lcm = a × b. Para 4 = 2² e 6 = 2 × 3, o mdc é 2 e o mmc é 2² × 3 = 12.
O algoritmo de Euclides encontra o mdc em O(log(min(a, b))) etapas. Em seguida, calcule a / gcd × b nessa ordem: o mdc divide a exatamente, então nada se perde, e nenhuma etapa excede a resposta. a × b / gcd causa estouro de um inteiro de 32 bits quando a = b = 10^6, pois o produto é 10^12 e a resposta é apenas 10^6.
Algoritmo
- Copie
aebparaxey. - Enquanto
ynão for0, substitua(x, y)por(y, x % y). Agora,xé o MDC. - Divida
aporx. - Multiplique o resultado por
be 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
- Calcular
a × bprimeiro. Em Java, C, C++, C# e Rust, o produto de dois números próximos de10^6excede o limite de um inteiro de 32 bits e resulta em um valor incorreto ou negativo (uma compilação de depuração do Rust causa panic), embora o mmc caiba. - Fazer a divisão em ponto flutuante. O resultado pode ser
2.146654199E9ou perder seus últimos dígitos; mantenha tudo em números inteiros. - Executar o loop de Euclides em
aebdiretamente. Depois, eles conterão o mdc e0, então trabalhe com cópias. - Presumir que a resposta é
a × b. Isso só vale quando os números não têm fatores em comum:lcm(4, 6)é12, não24.
Perguntas frequentes3
Qual é a fórmula para o MMC de dois números?
lcm(a, b) = a × b / gcd(a, b), calculado como a / gcd(a, b) × b para que nenhum valor intermediário exceda o resultado. Para 4 e 6, o mdc é 2, e 4 / 2 × 6 = 12.
Qual é a complexidade de tempo para calcular o MMC?
Com a fórmula do mdc, a complexidade de tempo é O(log(min(a, b))), o custo do algoritmo de Euclides, e a complexidade de espaço é O(1). Percorrer os múltiplos do número maior tem complexidade O(min(a, b)), e contar de um em um tem complexidade O(lcm(a, b)).
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 use inteiros de 64 bits quando a lista for longa.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def lcm(a, b):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumentos
a = 4 b = 6
Saída Esperada
12