Problem I
Euclid's GCD
One of the oldest known algorithms is a method for finding the greatest common divisor of two natural numbers. It turns out that you have already learned all you need to implement it.
Given two numbers $a$ and $b$, we keep doing the following until $b$ becomes $0$:
-
Calculate the remainder of dividing $a$ by $b$,
-
update $a$ to be the previous value of $b$ and $b$ to be the value of the remainder.
If at any time $b$ is $0$, then $a$ is the greatest common divisor of the original two numbers.
Input
Input consists of two lines. The first line consists of one integer $a$, where $0 \leq a \leq 10^{18}$. The second line consists of one integer $b$, where $0 \leq b \leq 10^{18}$.
Output
Output the greatest common divisor of $a$ and $b$.
| Sample Input 1 | Sample Output 1 |
|---|---|
0 3 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
12 15 |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
15 28 |
1 |
| Sample Input 4 | Sample Output 4 |
|---|---|
204 564 |
12 |
| Sample Input 5 | Sample Output 5 |
|---|---|
1495 715 |
65 |
