Least Common Multiple

Q: Qual è la formula per il m.c.m. di due numeri?

lcm(a, b) = a × b / gcd(a, b) , calcolato come a / gcd(a, b) × b in modo che nessun valore intermedio superi la risposta. Per 4 e 6 , il MCD è 2 e 4 / 2 × 6 = 12 .

Q: Qual è la complessità temporale del calcolo del mcm?

Con la formula del MCD, il tempo è O(log(min(a, b))) , pari al costo dell'algoritmo di Euclide, e lo spazio è O(1) . Procedere per multipli del numero più grande richiede O(min(a, b)) , mentre contare di uno in uno richiede O(lcm(a, b)) .

Q: 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 corrente cresce rapidamente, quindi usa interi a 64 bit quando la lista è lunga.

PrincipianteMatematica e simulazione

+10

Ricevi due numeri interi positivi a e b. Restituisci il loro minimo comune multiplo: il più piccolo numero intero positivo divisibile sia per a che per b senza resto.

Funzione

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

ainteger: il primo intero positivo
binteger: il secondo intero positivo
Restituisceinteger: il più piccolo intero positivo che è un multiplo sia di a sia di b

Vincoli

1 ≤ a ≤ 10⁶
1 ≤ b ≤ 10⁶
La risposta rientra in un intero con segno a 32 bit: lcm(a, b) ≤ 2³¹-1. Il prodotto a × b potrebbe non rientrarci.

Esempi

Input: a = 4b = 6
Output: 12
Spiegazione: I multipli di 6 iniziano con 6, 12, 18; i multipli di 4 iniziano con 4, 8, 12. Il primo numero presente in entrambe le liste è 12.

Input: a = 7b = 3
Output: 21
Spiegazione: 7 e 3 non hanno fattori in comune diversi da 1, quindi il loro minimo comune multiplo è il loro prodotto, 21.

Input: a = 15b = 45
Output: 45
Spiegazione: 15 divide esattamente 45, quindi 45 è già un multiplo di entrambi e non esiste alcun multiplo di 45 più piccolo.

Per approfondire

Riesci a trovare il MCD senza usare divisioni né resti, usando solo sottrazioni e dimezzamenti?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Il minimo comune multiplo e il massimo comune divisore sono legati da una proprietà: gcd(a, b) × lcm(a, b) = a × b. Quindi la risposta rapida è a × b / gcd(a, b). Il prodotto può arrivare a 10^12 e causare un overflow di un intero a 32 bit anche quando il risultato è rappresentabile, quindi dividi per il MCD prima di moltiplicare.

Conta in avanti dal numero più grande

Corretto, ma non termina sui test più grandi

Intuizione

La risposta è almeno il numero più grande. Imposta m su max(a, b) e aggiungi 1 finché entrambi i numeri non lo dividono; provi i candidati in ordine crescente, quindi il primo risultato è il più piccolo. Per 4 e 6 provi i numeri da 6 a 11 e ti fermi a 12. Il ciclo termina sempre, perché a × b è un multiplo comune.

Il numero di tentativi è circa pari alla grandezza della risposta. Per i numeri primi 46337 e 46327 la risposta è 2146654199, cioè più di due miliardi di tentativi.

Algoritmo

Imposta m al valore maggiore tra a e b.
Finché m % a o m % b non è 0, aggiungi 1 a m.
Restituisci m.

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

Procedi per multipli del numero più grande

Intuizione

La risposta deve essere un multiplo del numero più grande, big, quindi procedi per salti di big, 2 × big, 3 × big e fermati al primo numero divisibile per quello più piccolo. Per 4 e 6 provi 6, poi 12.

Poiché small × big è sempre un multiplo comune, il ciclo viene eseguito al massimo min(a, b) volte, al massimo un milione in questo caso. È abbastanza veloce per questi limiti, ma cresce comunque con l'input; con numeri fino a 10^18 non lo sarebbe.

Algoritmo

Sia big il numero più grande e small quello più piccolo.
Imposta m = big.
Finché m % small non è 0, aggiungi big a m.
Restituisci m.

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

Dividi per il MCD, poi moltiplica

Intuizione

Scomponi entrambi i numeri in fattori primi. Per ogni primo, il MCD prende la potenza minore tra le due e il mcm quella maggiore, quindi insieme usano ogni fattore di a e di b esattamente una volta: gcd × lcm = a × b. Per 4 = 2² e 6 = 2 × 3, il MCD è 2 e il mcm è 2² × 3 = 12.

L'algoritmo di Euclide trova il MCD in O(log(min(a, b))) passaggi. Poi calcola a / gcd × b in quest'ordine: il MCD divide a esattamente, quindi non si perde nulla e nessun passaggio supera il risultato. a × b / gcd va in overflow con un intero a 32 bit per a = b = 10^6, dove il prodotto è 10^12 e il risultato è solo 10^6.

Algoritmo

Copia a e b in x e y.
Mentre y non è 0, sostituisci (x, y) con (y, x % y). Ora x è il MCD.
Dividi a per x.
Moltiplica il risultato per b e 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

Calcolare prima a × b. In Java, C, C++, C# e Rust, il prodotto di due numeri vicini a 10^6 va in overflow con un intero a 32 bit e dà un risultato errato o negativo (una build di debug di Rust genera un panic), anche se l'lcm rientra nei limiti.
Dividere in virgola mobile. Il risultato può essere 2.146654199E9 oppure perdere le ultime cifre; usa solo interi.
Eseguire il ciclo di Euclide direttamente su a e b. Alla fine contengono il gcd e 0, quindi lavora su copie.
Supporre che la risposta sia a × b. Questo vale solo quando i numeri non hanno fattori in comune: lcm(4, 6) è 12, non 24.

Domande frequenti3

Qual è la formula per il m.c.m. di due numeri?

lcm(a, b) = a × b / gcd(a, b), calcolato come a / gcd(a, b) × b in modo che nessun valore intermedio superi la risposta. Per 4 e 6, il MCD è 2 e 4 / 2 × 6 = 12.

Qual è la complessità temporale del calcolo del mcm?

Con la formula del MCD, il tempo è O(log(min(a, b))), pari al costo dell'algoritmo di Euclide, e lo spazio è O(1). Procedere per multipli del numero più grande richiede O(min(a, b)), mentre contare di uno in uno richiede O(lcm(a, b)).

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 corrente cresce rapidamente, quindi usa interi a 64 bit quando la lista è lunga.

def lcm(a, b):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

a = 4
b = 6

Output atteso

Least Common Multiple

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Conta in avanti dal numero più grande

Procedi per multipli del numero più grande

Dividi per il MCD, poi moltiplica

Trappole e casi limite

Domande frequenti3

Problemi simili