Problema
Una pasticceria confeziona biscotti in scatole di tutte le misure da lo a hi. Vuole un'unica quantità di biscotti che riempia scatole di una qualsiasi di queste misure senza avanzi. La risposta è il più piccolo numero positivo divisibile per ogni intero da lo a hi, cioè il loro minimo comune multiplo.
Implementa smallest_multiple(lo, hi).
Input
lo: la misura di scatola più piccola.
hi: la misura di scatola più grande.
Output
Restituisci il più piccolo intero positivo divisibile senza resto per ciascuno di lo, lo + 1, ..., hi.
Vincoli
1 ≤ lo ≤ hi ≤ 40 (la risposta sta in un intero con segno a 64 bit)
Esempi
Input:
lo = 1
hi = 6
Output atteso:
expected = 60
Input:
long long lo = 1;
long long hi = 6;
Output atteso:
long long expected = 60;
Input:
long lo = 1;
long hi = 6;
Output atteso:
long expected = 60;
Spiegazione
60 è divisibile per 1, 2, 3, 4, 5 e 6, e nessun numero positivo più piccolo lo è, quindi la risposta è 60.
Input:
lo = 4
hi = 6
Output atteso:
expected = 60
Input:
long long lo = 4;
long long hi = 6;
Output atteso:
long long expected = 60;
Input:
long lo = 4;
long hi = 6;
Output atteso:
long expected = 60;
Spiegazione
mcm(4, 5) = 20 e mcm(20, 6) = 60, quindi la risposta è di nuovo 60: le misure piccole non aggiungono nulla.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Il mcm di un intero intervallo si può costruire un numero alla volta.
Suggerimento 2
mcm(a, b) = a / MCD(a, b) × b.
Suggerimento 3
Dividi prima di moltiplicare, così il valore intermedio non supera mai la risposta.
Complessità attesa
tempo O(n log M), spazio aggiuntivo O(1)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.