GCD of two numbers#1601

GCD of two numbers

1 second

128 megabytes

Very easy

Find the greatest common divisor (GCD) of two non-negative integers.

g cd (a, b) = ⎩ ⎨ ⎧ a, b, g cd (a mod b, b), g cd (a, b mod a), b = 0 a = 0 a \geq b a < b

\gcd(a, b) = \begin{cases} a, & b = 0 \\ b, & a = 0 \\ \gcd(a \bmod b,\, b), & a \ge b \\ \gcd(a,\, b \bmod a), & a < b \end{cases}

Input

Two integers $a$ and $b$ ( $0 \leq a, b \leq 2 \cdot 1 0^{9}$ 0 \leq a,\, b \leq 2 \cdot 10^9).

Print the greatest common divisor of $a$ and $b$ .

Example 1

Loading

g cd (a, b) = ⎩ ⎨ ⎧ a, b, g cd (a mod b, b), g cd (a, b mod a), b = 0 a = 0 a \geq b a < b

0 \leq a, b \leq 2 \cdot 1 0^{9}