Problème
Retournez le plus petit commun multiple de a et b, c'est-à-dire le plus petit nombre positif divisible par les deux. lcm(a, b) = a / gcd(a, b) × b.
Implémentez lcm(a, b).
Entrée
a : Le premier nombre positif. b : Le second nombre positif.
Sortie
Retournez lcm(a, b).
Contraintes
1 ≤ a, b ≤ 1 000 000 000
Exemples
Entrée :
a = 4
b = 6
Sortie attendue :
expected = 12Entrée :
long long a = 4;
long long b = 6;
Sortie attendue :
long long expected = 12;Entrée :
long a = 4;
long b = 6;
Sortie attendue :
long expected = 12;Explication
Multiples de 4 : 4, 8, 12… ; multiples de 6 : 6, 12… ; le premier commun est 12.
Entrée :
a = 7
b = 7
Sortie attendue :
expected = 7Entrée :
long long a = 7;
long long b = 7;
Sortie attendue :
long long expected = 7;Entrée :
long a = 7;
long b = 7;
Sortie attendue :
long expected = 7;Explication
Le PPCM d’un nombre avec lui-même est ce nombre : 7.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Utilisez la relation entre gcd et lcm au lieu de chercher les multiples.
Indice 2
Calculez d’abord le gcd, puis combinez les deux nombres avec précaution.
Indice 3
Divisez avant de multiplier pour réduire le risque de dépassement, même avec de grandes entrées.
Complexité attendue
temps O(log min(a, b)), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.