2743: 【例35.3】 最大公约数
内存限制：64 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：48
解决：35
题目描述
求两个正整数$m$，$n$的最大公约数。
输入
输入$m$，$n$。
输出
$m$，$n$的最大公约数,对于全部数据：$m$,$n$<$1000000$。
样例输入 复制
100 18样例输出 复制
2提示
辗转相除法
给定两个数，求这两个数的最大公约数欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。
例如：假如需要求 100 和18 两个正整数的最大公约数,用欧几里得算法，是这样进行的：
100 / 18 = 5 (余10)
18 / 10= 1 (余8)
10 / 8 = 1 (余2)
8 / 2 = 4 (余0)
至此，最大公约数为2
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 100 和 18 的最大公约数2。
假如求 18 和 100 两个数的最大公约数，即小的在前，大的在后：
18 / 100 = 0 (余18)
100 / 18 = 5 (余10)
......
结果与前面的一样。
#include<bits/stdc++.h>
using namespace std;
int m,n,r;
int main()
{
cin>>m>>n;
r=m%n;
while(r!=0) {
m=n;
n=r;
r=m%n;
}
cout<<n<<endl;
return 0;
}