Greatest common divisor (GCD) with subtraction

Given two positive integers a and b, you are asked to calculate the greatest common divisor of those. Yet, this time those numbers are way larger. So, finding all the divisors of each of those and then finding the largest common one won’t help. We should optimize the algorithm.
Let’s take the case where a > b. If we think about a common divisor d, both a and b are divisible by d. Meaning that:
where x and y are some integers. If we subtract b from a, we’ll get:
 
So, d is the divisor of both a and b, and as both x and y are integers ⇒ x-y is also an integer. Therefore as a-b = d(x-y), d should be a divisor of b - a. This observation is really helpful and can optimize the number of steps we perform in our program to find the GCD.
If the greatest common divisor d divides both a, b, and a-b, then we can find d by finding the greatest common divisor of b and a-b instead of a which was a larger number. We can repeat this process until either a or b turns 0 (in which case the nonzero element is the greatest divisor):
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)
Let’s run several simulations of the algorithm:
a = 8, b = 12
  1. b > a ⇒ swap ⇒ a = 12, b = 8 a = 12 - 8 = 4, b = 8
  1. b > a ⇒ swap ⇒ a = 8, b = 4 a = 8 - 4 = 4, b = 4
  1. a = 4 - 4 = 0, b = 4
  1. break ⇒ GCD = 4
a = 54, b = 24
  1. a = 54 - 24 = 30, b = 24
  1. a = 30 - 24 = 6, b = 24
  1. b > a ⇒ swap ⇒ a = 24, b = 6 a = 24 - 6 = 18, b = 6
  1. a = 18 - 6 = 12, b = 6
  1. a = 12 - 6 = 6, b = 6
  1. a = 6 - 6 = 0, b = 6
  1. break ⇒ GCD = 6
a = 17, b = 16
  1. a = 17 - 16 = 1, b = 16
  1. b > a ⇒ swap ⇒ a = 16, b = 1 a = 16 - 1 = 15, b = 1
  1. a = 14, b = 1
  1. a = 13, b = 1
  1. a = 12, b = 1
  1. a = 0, b = 1
  1. break ⇒ GCD = 1

Input

The only line of the input contains two integers a and b (0 ≤ a, b ≤ ).

Output

The program should print the greatest common divisor of a and b.

Examples

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