Algorithmes et Structures de Données

Plus grand commun diviseur (GCD) par soustraction

Étant donné deux entiers positifs a et b, vous devez calculer leur plus grand commun diviseur. Cependant, cette fois-ci, ces nombres peuvent être beaucoup plus grands. Par conséquent, énumérer tous les diviseurs de chacun pour ensuite identifier le plus grand en commun n’est pas envisageable. Nous devons donc optimiser l’algorithme.
Prenons le cas où a > b. Si nous considérons un diviseur commun d, alors a et b sont tous deux divisibles par d. Cela signifie :
où x et y sont des entiers. En soustrayant b à a, on obtient :
 
Ainsi, d est un diviseur de a et b, et comme x et y sont des entiers, x-y l’est aussi. Donc, étant donné que a-b = d(x-y), d doit aussi être un diviseur de a-b. Cette observation est précieuse pour réduire le nombre d’opérations nécessaires à la recherche du GCD.
Si le plus grand commun diviseur d divise a, b et a-b, alors nous pouvons trouver d en calculant le plus grand commun diviseur de b et a-b, au lieu de celui de a (qui était plus grand). Nous pouvons répéter ce processus jusqu’à ce que a ou b devienne 0 (auquel cas l’entier non nul est le plus grand diviseur) :
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)
Examinons maintenant plusieurs simulations de cet algorithme :
a = 8, b = 12
  1. b > a ⇒ échange ⇒ a = 12, b = 8
  1. b > a ⇒ échange ⇒ a = 8, b = 4
  1. a = 4 - 4 = 0, b = 4
  1. fin ⇒ GCD = 4
a = 54, b = 24
  1. a = 54 - 24 = 30, b = 24
  1. a = 30 - 24 = 6, b = 24
  1. b > a ⇒ échange ⇒ 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. fin ⇒ GCD = 6
a = 17, b = 16
  1. a = 17 - 16 = 1, b = 16
  1. b > a ⇒ échange ⇒ 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. fin ⇒ GCD = 1

Entrée

La seule ligne d’entrée contient deux entiers a et b (0 ≤ a, b ≤ ).

Sortie

Le programme doit afficher le plus grand commun diviseur de a et b.

Exemples

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