最大公约数

题目描述

定义两个正整数的最大公约数 \(\gcd(a,b)\) 为最大的正整数 \(d\)，使得 \(d\) 可以同时整除 \(a\) 和 \(b\)。

例如，\(\gcd(9,12)=3\)，因为 \(9\div 3\) 和 \(12\div 3\) 的余数是 \(0\)，而无法找到一个比 \(3\) 更大的正整数满足要求。

现在给定两个正整数 \(a,b\)，要求出 \(\gcd(a,b)\)。

输入格式

输入两个正整数 \(a,b\)。

输出格式

输出 \(\gcd(a,b)\)。

输入输出样例 #1

输入 #1

9 12

输出 #1

3

输入输出样例 #2

输入 #2

100 1000

输出 #2

100

说明/提示

对于 \(40\%\) 的数据，\(1\leq a,b\leq 1000\)。

对于所有的数据，\(1\leq a,b\leq 10^9\)。