Algoritmi e Strutture Dati

Massimo comune divisore (GCD) con la sottrazione

Dati due interi positivi a e b, devi calcolare il loro massimo comune divisore. Questa volta, però, i numeri possono essere molto grandi. Pertanto, trovare tutti i divisori di ciascuno e poi determinare il più grande in comune non sarebbe efficiente. Occorre ottimizzare l’algoritmo.
Consideriamo il caso in cui a > b. Se pensiamo a un divisore comune d, sia a sia b sono divisibili per d. Ovvero:
dove x e y sono due interi. Se sottraiamo b da a, otteniamo:
 
Quindi, se d è un divisore comune di a e b, allora è anche un divisore di a-b. Questa osservazione è molto utile e può ridurre il numero di passaggi necessari nel programma per trovare il GCD.
Se il massimo comune divisore d divide sia a sia b, oltre a dividere anche a-b, allora possiamo continuare la ricerca di d calcolando il GCD di b e a-b (invece di usare a). Ripetiamo questo processo finché uno tra a o b non diventa 0 (in tal caso, l’altro valore è il divisore comune massimo):
a, b = int(input()), int(input())
while a > 0 and b > 0:  # In case a or b is 0 => the other one is the GCD
    if b > a:           # Let's always keep a >= b
        a, b = b, a     # Swap the numbers
    a, b = a - b, b     # gcd of (a, b) is the same as gcd of (a, b - a)

d = b if a == 0 else a  # if a is 0 => b is GCD, if b is 0 => a is GCD
print('gcd:', d)
Di seguito alcune simulazioni dell’algoritmo:
a = 8, b = 12
  1. b > a ⇒ scambio ⇒ a = 12, b = 8
  1. b > a ⇒ scambio ⇒ a = 8, b = 4
  1. a = 4 - 4 = 0, b = 4
  1. uscita ⇒ GCD = 4
a = 54, b = 24
  1. a = 54 - 24 = 30, b = 24
  1. a = 30 - 24 = 6, b = 24
  1. b > a ⇒ scambio ⇒ a = 24, b = 6
  1. a = 18 - 6 = 12, b = 6
  1. a = 12 - 6 = 6, b = 6
  1. a = 6 - 6 = 0, b = 6
  1. uscita ⇒ GCD = 6
a = 17, b = 16
  1. a = 17 - 16 = 1, b = 16
  1. b > a ⇒ scambio ⇒ a = 16, b = 1
  1. a = 14, b = 1
  1. a = 13, b = 1
  1. a = 12, b = 1
  1. …
  1. …
  1. a = 0, b = 1
  1. uscita ⇒ GCD = 1

Input

L’unica riga di input contiene due interi a e b (0 ≤ a, b ≤ ).

Output

Il programma deve stampare il massimo comune divisore di a e b.

Esempi

Input
Output
8 12
4
54 24
6
17 16
1

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue