Problema
Uma padaria embala biscoitos em caixas de todos os tamanhos de lo a hi. Ela quer uma única quantidade por fornada que encha caixas de qualquer um desses tamanhos sem sobrar nada. A resposta é o menor número positivo divisível por todos os inteiros de lo a hi, ou seja, o mínimo múltiplo comum (MMC) deles.
Implemente smallest_multiple(lo, hi).
Entrada
lo: o menor tamanho de caixa.
hi: o maior tamanho de caixa.
Saída
Retorne o menor inteiro positivo que é divisível, sem resto, por cada um de lo, lo + 1, ..., hi.
Restrições
1 ≤ lo ≤ hi ≤ 40 (a resposta cabe em um inteiro de 64 bits com sinal)
Exemplos
Entrada:
lo = 1
hi = 6
Saída esperada:
expected = 60
Entrada:
long long lo = 1;
long long hi = 6;
Saída esperada:
long long expected = 60;
Entrada:
long lo = 1;
long hi = 6;
Saída esperada:
long expected = 60;
Explicação
60 é divisível por 1, 2, 3, 4, 5 e 6, e nenhum número positivo menor é, então a resposta é 60.
Entrada:
lo = 4
hi = 6
Saída esperada:
expected = 60
Entrada:
long long lo = 4;
long long hi = 6;
Saída esperada:
long long expected = 60;
Entrada:
long lo = 4;
long hi = 6;
Saída esperada:
long expected = 60;
Explicação
mmc(4, 5) = 20 e mmc(20, 6) = 60, então a resposta é 60 de novo: os tamanhos pequenos não acrescentaram nada.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
O mmc de um intervalo inteiro pode ser construído um número de cada vez.
Dica 2
mmc(a, b) = a / mdc(a, b) × b.
Dica 3
Divida antes de multiplicar, para que o valor intermediário nunca fique maior que a resposta.
Complexidade esperada
tempo O(n log M), espaço extra O(1)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.