Algorithms and Data Structures

• Status
• 1
Implementation
• 2
Bitwise operations
• 3
Prefix Sums
• 4
Sliding window / Two pointers
• 5
Modular Arithmetic
• 6
Number Theory
• 7
Binary Search
• 8
Basic Sorting
• 9
Greedy Algorithms
• 10
Basic Dynamic Programming
• 11
Recursion
• 12
• 13
Queue & Stack
• 14
Binary tree + BST
• 15
Divide & Conquer + Advanced Sorting
• 16
Heap
• 17
Hashing
• 18
Graph Representation
• 19
BFS

• # GCD - Euclid’s algorithm

After running several iterations of the algorithm, we start to notice that there are some redundant operations, and the algorithm of finding the greatest common divisor can actually be optimized.
With subtraction, we keep subtracting the smaller number from the larger number until we get a result of 0 or a number that is equal to the GCD. We can speed that up by finding the remainder of the larger number divided by the smaller one. With the modulo operation, we keep dividing the larger number by the smaller number and taking the remainder until the remainder is 0. The last non-zero remainder we get is the GCD.
Think of the modulo operation as a more efficient way of finding the GCD. Instead of subtracting the smaller number from the larger number repeatedly, you are using division to reduce the larger number. This means that you are dividing both numbers by their common divisors and so converging to the greatest common divisor much faster.
``````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
a, b = b, a % b       # gcd of (a, b) is the same as gcd of (b, a % b)

d = b if a == 0 else a  # if a is 0 => b is GCD, if b is 0 => a is GCD
print('gcd:', d)``````
This algorithm was first mentioned in Euclid’s book written in 300 BC.

Let’s run several simulations of the algorithm:
a = 8, b = 12
1. a = 12, b = 8
1. a = 8, b = 4
1. a = 4, b = 0
1. break ⇒ GCD = 4
a = 54, b = 24
1. a = 24, b = 6
1. a = 6, b = 0
1. break ⇒ GCD = 6
a = 17, b = 16
1. a = 16, b = 1
1. a = 1, b = 0
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: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB