Problème
Une boulangerie emballe ses biscuits dans des boîtes de toutes les tailles, de lo à hi. Elle cherche une taille de fournée qui remplisse exactement des boîtes de n'importe laquelle de ces tailles, sans reste. La réponse est le plus petit entier positif divisible par tous les entiers de lo à hi, autrement dit leur plus petit commun multiple (PPCM).
Implémentez smallest_multiple(lo, hi).
Entrée
lo : la plus petite taille de boîte.
hi : la plus grande taille de boîte.
Sortie
Renvoyez le plus petit entier strictement positif divisible sans reste par chacun des entiers lo, lo + 1, ..., hi.
Contraintes
1 ≤ lo ≤ hi ≤ 40 (la réponse tient dans un entier signé sur 64 bits)
Exemples
Entrée :
lo = 1
hi = 6
Sortie attendue :
expected = 60
Entrée :
long long lo = 1;
long long hi = 6;
Sortie attendue :
long long expected = 60;
Entrée :
long lo = 1;
long hi = 6;
Sortie attendue :
long expected = 60;
Explication
60 est divisible par 1, 2, 3, 4, 5 et 6, et aucun entier positif plus petit ne l'est, donc la réponse est 60.
Entrée :
lo = 4
hi = 6
Sortie attendue :
expected = 60
Entrée :
long long lo = 4;
long long hi = 6;
Sortie attendue :
long long expected = 60;
Entrée :
long lo = 4;
long hi = 6;
Sortie attendue :
long expected = 60;
Explication
PPCM(4, 5) = 20 et PPCM(20, 6) = 60, donc la réponse est encore 60 : les petites tailles n'apportaient rien.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Le PPCM de tout un intervalle se construit un nombre à la fois.
Indice 2
PPCM(a, b) = a / PGCD(a, b) × b.
Indice 3
Divisez avant de multiplier pour que la valeur intermédiaire ne dépasse jamais la réponse.
Complexité attendue
temps O(n log M), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.