Tutte le sfide
Facile 0 risolte 0% di accettazione

Minimo comune multiplo di un intervallo

Trova il più piccolo numero positivo divisibile per ogni intero di un intervallo.

Cosa imparerai

  • Calcolare mcm(a, b) a partire da MCD(a, b)
  • Applicare un'operazione in cascata a un intervallo di numeri
  • Evitare che i valori intermedi vadano in overflow

Problema

Una pasticceria confeziona biscotti in scatole di tutte le misure da lo a hi. Vuole un'unica quantità di biscotti che riempia scatole di una qualsiasi di queste misure senza avanzi. La risposta è il più piccolo numero positivo divisibile per ogni intero da lo a hi, cioè il loro minimo comune multiplo.

Implementa smallest_multiple(lo, hi).

Input

lo: la misura di scatola più piccola.

hi: la misura di scatola più grande.

Output

Restituisci il più piccolo intero positivo divisibile senza resto per ciascuno di lo, lo + 1, ..., hi.

Vincoli

1 ≤ lo ≤ hi ≤ 40 (la risposta sta in un intero con segno a 64 bit)

Esempi

Esempio 1
Input:
lo = 1
hi = 6

Output atteso:
expected = 60
Input:
long long lo = 1;
long long hi = 6;

Output atteso:
long long expected = 60;
Input:
long lo = 1;
long hi = 6;

Output atteso:
long expected = 60;

Spiegazione

60 è divisibile per 1, 2, 3, 4, 5 e 6, e nessun numero positivo più piccolo lo è, quindi la risposta è 60.

Esempio 2
Input:
lo = 4
hi = 6

Output atteso:
expected = 60
Input:
long long lo = 4;
long long hi = 6;

Output atteso:
long long expected = 60;
Input:
long lo = 4;
long hi = 6;

Output atteso:
long expected = 60;

Spiegazione

mcm(4, 5) = 20 e mcm(20, 6) = 60, quindi la risposta è di nuovo 60: le misure piccole non aggiungono nulla.

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

Il mcm di un intero intervallo si può costruire un numero alla volta.

Suggerimento 2

mcm(a, b) = a / MCD(a, b) × b.

Suggerimento 3

Dividi prima di moltiplicare, così il valore intermedio non supera mai la risposta.

Complessità attesa

tempo O(n log M), spazio aggiuntivo O(1)

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.