Least Common Multiple
Ricevi due interi positivi a e b. Restituisci il loro minimo comune multiplo: il più piccolo intero positivo che sia divisibile sia per a sia per b senza resto.
Per esempio, i multipli di 6 sono 6, 12, 18, 24 e così via; i multipli di 8 sono 8, 16, 24 e così via, e il primo numero presente in entrambe le liste è 24.
Funzione
- ainteger
- il primo intero positivo
- binteger
- il secondo intero positivo
- Restituisceinteger
- il più piccolo intero positivo multiplo sia di a sia di b
Vincoli
1 ≤ a ≤ 1061 ≤ b ≤ 106- La risposta rientra in un intero con segno a 32 bit:
lcm(a, b) ≤ 231-1. Il prodottoa × bpotrebbe non rientrarci.
Esempi
- Input
- a = 4b = 6
- Output
- 12
- Spiegazione
- I multipli di
6iniziano con 6, 12, 18; i multipli di4iniziano con 4, 8, 12. Il primo numero presente in entrambi gli elenchi è12.
- Input
- a = 7b = 3
- Output
- 21
- Spiegazione
7e3non hanno fattori in comune oltre a1, quindi il loro minimo comune multiplo è il loro prodotto,21.
- Input
- a = 15b = 45
- Output
- 45
- Spiegazione
15divide esattamente45, quindi45è già un multiplo di entrambi e non esiste alcun multiplo di45più piccolo.
+15 test nascosti all’invio
Per approfondire
Riesci a trovare il MCD senza usare divisioni o resti, usando solo sottrazioni e dimezzamenti?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
La risposta è un multiplo del numero più grande. Devi provare tutti i numeri intermedi oppure solo i multipli del numero più grande?
Il massimo comune divisore e il minimo comune multiplo sono collegati:
gcd(a, b) × lcm(a, b) = a × b. L'algoritmo di Euclide trova il MCD in poche decine di passaggi.Calcola l'MCD, poi restituisci
a / gcd × b. Dividi prima: il prodottoa × bpuò causare un overflow di un intero a 32 bit anche quando il risultato è rappresentabile.
Soluzione
Il minimo comune multiplo e il massimo comune divisore sono due facce della stessa realtà: gcd(a, b) × lcm(a, b) = a × b. Quindi la risposta rapida è a × b / gcd(a, b), con un piccolo accorgimento. Il prodotto può arrivare a 10^12, valore che causa un overflow in un intero a 32 bit anche quando il risultato è rappresentabile; perciò dividi per il MCD prima di moltiplicare.
Conta in avanti a partire dal numero più grande
Corretto, ma non termina sui test più grandi
Intuizione
La risposta è un multiplo di entrambi i numeri, quindi è almeno grande quanto il maggiore dei due. Inizia un candidato m a max(a, b) e aggiungi 1 finché sia a sia b non lo dividono. Provi i candidati in ordine crescente, quindi il primo che funziona è il minimo.
Per 4 e 6 provi 6, 7, 8, 9, 10 e 11, che non funzionano, e ti fermi a 12. Il ciclo termina sempre, perché a × b è un multiplo comune.
Il numero di tentativi è approssimativamente pari alla grandezza della risposta. Per 46337 e 46327, due numeri primi, la risposta è 2146654199, quindi il ciclo viene eseguito oltre due miliardi di volte. È decisamente troppo lento.
Algoritmo
- Imposta
mal valore maggiore traaeb. - Finché
m % aom % bè diverso da0, aggiungi 1 am. - Restituisci
m.
def lcm(a, b):
m = max(a, b)
while m % a != 0 or m % b != 0:
m += 1
return mProcedi attraverso i multipli del numero maggiore
Intuizione
La maggior parte dei candidati nel conteggio è inutile: la risposta deve essere un multiplo del numero più grande, che chiamiamo big. Quindi passa direttamente da un multiplo di big al successivo: big, 2 × big, 3 × big, e fermati al primo che è divisibile per il numero più piccolo.
Per 4 e 6 provi 6 (4 non lo divide) e poi 12 (lo divide). La risposta è k × big per qualche k, e k è al massimo il numero più piccolo, perché small × big è sempre un multiplo comune. Quindi il ciclo viene eseguito al massimo min(a, b) volte, che qui non sono mai più di un milione.
Qui è abbastanza veloce, ma cresce comunque con l’input. Con numeri fino a 10^18 non lo sarebbe.
Algoritmo
- Sia
bigil numero più grande esmallquello più piccolo. - Imposta
m = big. - Finché
m % smallnon è0, aggiungibigam. - Restituisci
m.
def lcm(a, b):
big, small = max(a, b), min(a, b)
m = big
while m % small != 0:
m += big
return mDividi per il MCD, poi moltiplica
Intuizione
Scomponi entrambi i numeri in fattori primi. Il gcd prende ogni fattore primo con l’esponente minore tra i due, mentre il lcm prende quello maggiore; insieme utilizzano ogni fattore di a e di b esattamente una volta. Si ottiene così gcd(a, b) × lcm(a, b) = a × b, quindi lcm(a, b) = a × b / gcd(a, b). Per 4 = 2² e 6 = 2 × 3, il gcd è 2 e il lcm è 2² × 3 = 12.
Trova il gcd con l’algoritmo di Euclide: sostituisci (x, y) con (y, x % y) finché y non è 0. Servono O(log(min(a, b))) passaggi.
Poi calcola a / gcd × b, in quest’ordine. Il gcd divide a esattamente, quindi la divisione non comporta alcuna perdita e il risultato non supera mai la risposta. Scrivere invece a × b / gcd causa un overflow di un intero a 32 bit con a = b = 10^6: il prodotto è 10^12, mentre la risposta è solo 10^6.
Algoritmo
- Copia
aebinxey. - Mentre
ynon è0, sostituisci(x, y)con(y, x % y). Oraxè il MCD. - Dividi
aperx. - Moltiplica il risultato per
be restituiscilo.
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
Trappole e casi limite
La formula è su una riga, e i bug dipendono dall’ordine delle operazioni aritmetiche.
- Calcolare prima
a × b. In Java, C, C++, C# e Rust il prodotto di due numeri vicini a10^6supera il limite di un intero a 32 bit e il risultato è errato o negativo (invece, una build di debug di Rust va in panic), anche se il vero mcm rientra nell’intervallo. - Dividere
a × bper il MCD usando i numeri in virgola mobile. Il risultato può essere2.146654199E9oppure perdere le ultime cifre; usa solo numeri interi. - Eseguire il ciclo di Euclide direttamente su
aeb, per poi usarli nella formula. Dopo il ciclo contengono il MCD e0, quindi lavora su copie. - Supporre che il risultato sia
a × b. Questo vale solo quando i due numeri non hanno fattori in comune:lcm(4, 6)è12, non24.
Domande frequenti4
Qual è la formula per il mcm di due numeri?
lcm(a, b) = a × b / gcd(a, b), calcolato come a / gcd(a, b) × b, così il valore intermedio non supera mai il risultato. Per 4 e 6, il MCD è 2 e 4 / 2 × 6 = 12.
Perché gcd(a, b) × lcm(a, b) è uguale a a × b?
Per ogni numero primo, il MCD usa la potenza minore tra quelle in a e b, mentre il mcm usa quella maggiore. La potenza minore più quella maggiore è la somma di entrambe le potenze, che corrisponde esattamente alla potenza di quel numero primo in a × b. Ogni numero primo corrisponde, quindi i due prodotti sono uguali.
Qual è la complessità temporale del calcolo del mcm?
Con la formula del MCD è O(log(min(a, b))), il costo dell'algoritmo di Euclide, più una divisione e una moltiplicazione. Richiede O(1) spazio aggiuntivo. Cercare tra i multipli è molto più lento: O(min(a, b)) quando si procede a passi pari al numero più grande e O(lcm(a, b)) quando si conta di uno in uno.
Come si trova il minimo comune multiplo di più di due numeri?
Riduci la lista: lcm(a, b, c) = lcm(lcm(a, b), c). Per [4, 6, 10], lcm(4, 6) = 12 e lcm(12, 10) = 60. Il valore accumulato cresce rapidamente, quindi fai attenzione all’overflow e usa interi a 64 bit quando la lista è lunga.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def lcm(a, b):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
a = 4 b = 6
Atteso
12