Minimo comune multiplo (LCM)
Il minimo comune multiplo di due numeri
a e b è il più piccolo numero che sia divisibile sia da a che da b. In altre parole, cerchiamo un valore l (minimo comune multiplo) tale che e , dove x e y sono numeri interi positivi (2 ≤ x, y).Un approccio semplice, ma poco efficiente, consiste nell’iterare tra i multipli di
a (1·a, 2·a, 3·a, ...) e controllare ogni volta se quel valore è divisibile da b. Tuttavia, questo metodo può diventare molto lento. Se, per esempio, a e b fossero 13 e 17, si dovrebbe calcolare 1·13, 2·13, …, fino a 17·13 per trovare il primo valore divisibile sia da 13 sia da 17.È vero che
a·b è sempre un multiplo comune di a e b, ma non è detto che sia il più piccolo. Nel caso di 13 e 17, risulta effettivamente il minimo; in altri casi come 8 e 12, non lo è. In generale, il MCM di a e b è dato dal prodotto a·b diviso per il loro massimo comun divisore:L’idea di questa formula si basa sul fatto che il MCM è il più piccolo multiplo di entrambi i numeri che contenga tutti i loro fattori primi. Dato che il massimo comun divisore di due numeri rappresenta il prodotto dei loro fattori primi comuni, dividendo il prodotto
a·b per gcd(a, b) si eliminano i fattori duplicati, ottenendo esattamente il MCM.Per trovare il MCM di due numeri, è dunque sufficiente eseguire la fattorizzazione prima di ciascun numero e poi moltiplicare la potenza massima di ogni fattore primo che compare in almeno una delle due fattorizzazioni.
In questo senso, il prodotto
a·b mette insieme tutti i fattori primi di a e b sommando gli esponenti. Invece, gcd(a, b) rimuove la parte corrispondente agli esponenti minimi da ogni fattore, lasciando così i massimi. Il risultato è precisamente il MCM di a e b.Ingresso
L’unica riga dell’ingresso contiene due interi
a e b (1 ≤ a, b ≤ ).Uscita
Il programma deve stampare il minimo comune multiplo di
a e b.Esempi
Ingresso | Uscita |
8 12 | 24 |
54 24 | 216 |
17 16 | 272 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB