A71248. 求最大公约数问题
编程题
基础
知识点
题目描述
给定两个正整数，求它们的最大公约数。
输入格式
输入一行，包含两个正整数( < 1,000,000,000 )。
输出格式
输出一个正整数，即这两个正整数的最大公约数。
输入输出样例
输入 #1
6 9
输出 #1
3
说明/提示
提示
求最大公约数可以使用辗转相除法：
假设 a > b > 0，那么 a 和 b 的最大公约数等于 b 和 a \% b 的最大公约数。
然后把 b 和 a \% b 作为新一轮的输入。
由于这个过程会一直递减，直到 a \% b 等于 0 的时候，b 的值就是所要求的最大公约数。
比如： 9 和 6 的最大公约数等于 6 和 9\%6=3 的最大公约数。 由于 6 \% 3==0，所以最大公约数为 3。