欧几里德算法
题目描述
欧几里得算法（辗转相除法）基于这样一个原理：
两个整数的最大公约数（GCD）等于其中较小的数与两数相除的余数的最大公约数。换句话说，我们可以通过将较大的数除以较小的数，求得余数，然后将原问题转化为求较小的数与余数的最大公约数。
这个过程可以不断重复，直到余数为零，此时较小的数即为最大公约数。
gcd(a, b) = gcd(b, a % b)
输入格式
两行整数，分别是整数 和 ，满足 。
输出格式
两个正整数的最大公约数。
120
36
12
欧几里得算法（辗转相除法）基于这样一个原理：
两个整数的最大公约数（GCD）等于其中较小的数与两数相除的余数的最大公约数。换句话说，我们可以通过将较大的数除以较小的数，求得余数，然后将原问题转化为求较小的数与余数的最大公约数。
这个过程可以不断重复，直到余数为零，此时较小的数即为最大公约数。
gcd(a, b) = gcd(b, a % b)
两行整数，分别是整数 和 ，满足 。
两个正整数的最大公约数。
120
36
12