Greatest Common Divisor

Q: Qual è la complessità temporale dell’algoritmo di Euclide?

Viene eseguito in O(log(min(a, b))) passaggi, perché ogni due passaggi dimezza almeno il numero più grande. Il caso peggiore è una coppia di numeri di Fibonacci consecutivi. Per numeri fino a 10^9 , sono al massimo 43 passaggi, e l'algoritmo usa O(1) spazio aggiuntivo.

Q: Perché gcd(a, b) è uguale a gcd(b, a % b)?

Scrivi a = q × b + r con r = a % b . Un numero che divide a e b divide a - q × b , che è r . Un numero che divide b e r divide q × b + r , che è a . Entrambe le coppie hanno gli stessi divisori comuni, quindi hanno anche il massimo divisore comune.

PrincipianteMatematica e simulazione

+10

Ti vengono dati due numeri interi positivi a e b. Restituisci il loro massimo comune divisore: il più grande numero intero che divide entrambi senza resto.

Per esempio, i numeri che dividono sia 8 sia 12 sono 1, 2 e 4, quindi la risposta è 4.

Funzione

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

ainteger: il primo intero positivo
binteger: il secondo intero positivo
Restituisceinteger: il più grande intero che divide sia a sia b

Vincoli

1 ≤ a ≤ 10⁹
1 ≤ b ≤ 10⁹

Esempi

Input: a = 12b = 18
Output: 6
Spiegazione: I divisori di 12 sono 1, 2, 3, 4, 6 e 12; i divisori di 18 sono 1, 2, 3, 6, 9 e 18. Il più grande presente in entrambe le liste è 6.

Input: a = 17b = 5
Output: 1
Spiegazione: 17 e 5 sono entrambi numeri primi e diversi, quindi l’unico divisore che hanno in comune è 1.

Input: a = 42b = 42
Output: 42
Spiegazione: Un numero divide sé stesso e niente di più grande di 42 può dividere 42, quindi il massimo comune divisore di 42 e 42 è 42.

+14 test nascosti all’invio

Per approfondire

Puoi estendere l'algoritmo di Euclide in modo che restituisca anche gli interi x e y tali che a × x + b × y = gcd(a, b)?

Suggerimenti

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

0 di 3 aperti

Soluzione

La definizione suggerisce di provare i candidati uno alla volta, e questo funziona con i numeri piccoli. Con a e b fino a 10^9, però, due numeri grandi che non hanno fattori in comune richiedono un miliardo di tentativi. L’osservazione di Euclide secondo cui gcd(a, b) è uguale a gcd(b, a % b) riduce i numeri così rapidamente che nessuna coppia fino a 10^9 richiede più di 43 passaggi.

Conta alla rovescia partendo dal numero più piccolo

Corretto, ma non termina sui test più grandi

Intuizione

Nessun divisore comune può essere maggiore del minore dei due numeri, perché un divisore di b è al massimo b. Quindi inizia con un candidato d pari a min(a, b) e decrementalo di uno finché non divide entrambi. Poiché provi i candidati dall’alto, il primo che funziona è il massimo.

Per 12 e 18 provi 12 (non divide 18), poi 11, 10, 9, 8 e 7, che non funzionano, e ti fermi a 6. Il ciclo termina sempre, perché 1 divide ogni numero.

Il costo è il numero di candidati. Per 999999937 e 999999929, che sono numeri primi, la risposta è 1 e il ciclo viene eseguito quasi 10^9 volte. È troppo lento per i test più grandi.

Algoritmo

Imposta d sul minore tra a e b.
Finché a % d o b % d non è 0, sottrai 1 da d.
Restituisci d.

def gcd(a, b):
    d = min(a, b)
    while a % d != 0 or b % d != 0:
        d -= 1
    return d

Algoritmo di Euclide

Intuizione

Scrivi a = q × b + r, dove r = a % b. Qualsiasi numero che divide sia a sia b divide anche r = a - q × b. Qualsiasi numero che divide sia b sia r divide anche a = q × b + r. Quindi le coppie (a, b) e (b, r) hanno esattamente gli stessi divisori comuni e lo stesso massimo divisore comune.

Sostituisci (a, b) con (b, a % b) e ripeti finché b diventa 0. Ogni numero divide 0, quindi gcd(a, 0) = a e a è la risposta. Per 12 e 18: (12, 18) diventa (18, 12), poi (12, 6), poi (6, 0), e la risposta è 6. Il primo passaggio scambia da solo i numeri quando a è più piccolo, quindi non devi mai ordinarli.

Ogni due passaggi il numero più grande si dimezza almeno, quindi il ciclo viene eseguito O(log(min(a, b))) volte. Gli input più lenti sono numeri di Fibonacci consecutivi, come 701408733 e 433494437, e anche in quel caso bastano solo 42 passaggi.

Algoritmo

Finché b non è 0, calcola r = a % b.
Imposta a = b e b = r.
Quando b raggiunge 0, restituisci a.

def gcd(a, b):
    # gcd(a, b) == gcd(b, a % b), and gcd(a, 0) == a.
    while b != 0:
        a, b = b, a % b
    return a

Trappole e casi limite

L'algoritmo è breve, quindi gli errori dipendono dall'aggiornamento e dalla condizione di arresto.

Aggiornare nell'ordine sbagliato. a = b seguito da b = a % b calcola b % b, che è sempre 0, e restituisce b. Salva prima il resto in una variabile temporanea oppure assegna entrambi i valori contemporaneamente.
Restituire b invece di a quando il ciclo termina. A quel punto b è 0.
Fermare il conto alla rovescia a 2 o iniziarlo da max(a, b). Il primo caso non considera coppie coprime come 17 e 5; il secondo fa perdere tempo con candidati che non possono dividere il numero più piccolo.
Usare sottrazioni ripetute invece del resto. gcd(10^9, 1) richiede quindi un miliardo di sottrazioni; % le esegue tutte in un solo passaggio.

Domande frequenti4

Qual è la complessità temporale dell’algoritmo di Euclide?

Viene eseguito in O(log(min(a, b))) passaggi, perché ogni due passaggi dimezza almeno il numero più grande. Il caso peggiore è una coppia di numeri di Fibonacci consecutivi. Per numeri fino a 10^9, sono al massimo 43 passaggi, e l'algoritmo usa O(1) spazio aggiuntivo.

Perché gcd(a, b) è uguale a gcd(b, a % b)?

Scrivi a = q × b + r con r = a % b. Un numero che divide a e b divide a - q × b, che è r. Un numero che divide b e r divide q × b + r, che è a. Entrambe le coppie hanno gli stessi divisori comuni, quindi hanno anche il massimo divisore comune.

Qual è la differenza tra MCD e mcm?

Il massimo comune divisore è il numero più grande che divide entrambi gli input; il minimo comune multiplo è il numero più piccolo che è divisibile per entrambi gli input. Sono collegati dalla relazione gcd(a, b) × lcm(a, b) = a × b, quindi, una volta ottenuto il MCD, il MCM è a / gcd(a, b) × b.

Qual è il MCD di due numeri coprimi?

Due numeri sono coprimi quando il loro massimo comune divisore è 1, ovvero quando non hanno fattori primi in comune. Due numeri primi diversi sono sempre coprimi, così come due interi consecutivi qualsiasi, come 8 e 9.

Python

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

Casi di test

Caso 1

Caso 2

Caso 3

Input

a = 12
b = 18

Atteso