soho做网站多少钱/百度推广投诉中心

最大公约数与最小公倍数

---

题目描述

输入两个正整数m和n，求其最大公约数和最小公倍数。

输入格式

两个整数

输出格式

最大公约数，最小公倍数

样例输入

5 7

样例输出

1 35

题目思路

在这里我们用m表示较大的那个数，n表示较小的数。求最大公约数也即是求能被m和n 整除的最大数。gcd(m,n) 表示m 和n 的最大公约数。根据辗转相除法可知gcd(m,n)=gcd(n,m%n),具体证明过程如下：

---

$\gcd (m,n)=\gcd (n,m\mathrm{mod}n)$ (不妨设 $m>n$ 且 $r=m\mathrm{mod}n,r\ne 0$ )

$m$ 可以表示成 $m=kn+r(m,n,k,r$ 皆为正整数, 且 $r<n)$ ，则 $r=m\mathrm{mod}n$, 假设 $d$ 是 $m,n$ 的一个公约数，即 $m$ 和 $n$ 都可以被 $d$ 整除。
而 $r=m-kn$,两边同时除以 $d$ ，可得:
$$\frac{r}{d}=\frac{m}{d}-\frac{kn}{d}=h$$
由等式右边可知 $h$ 为整数（ $d$ 是 $m$ 和 $n$ 的公约数， $kn$ 是 $n$ 的整倍数，所以 $\frac{kn}{d}$ 也应该是整数），所 以我们得出 $d$ 也为 $m$ 和 $n$ 的余数的公约数即 $d$ 是 $n，m\mathrm{mod}n$ 的公约数
至此，我们得知，如果一个数是两个数的公约数，那么，它也是这两个数的余数和较小数公约数。
假设 $d$ 是 $(n,m\mathrm{mod}n)$ 的任意一个公约数，则 $d$ 是 $n$ 的公约数， $d$ 是 $(m-kn)$ 的公约数， $k$ 是一个整数，
我们假设 $n=xd,m-kn=yd$ 其中 $x,y$ 是正整数，根据上面的推断可得:
$$m=yd+kn$$
两边同时除以 $d$ ，得
$$\frac{m}{d}=y+\frac{kn}{d}$$
由已知可得 $y$ 为正整数， $d$ 是 $m$ 的公约数， $\frac{kn}{d}$ 也肯定是正整数，故得 $d$ 为 $m$ 的公约数.
因为 $d$ 既是 $n$ 的公约数又是 $m$ 的公约数了，
所以证出 $(m,n)$ 和 $(n,m\mathrm{mod}n)$ 的公约数是一样的，其最大公约数也必然相等。

---

所以求m和n的最大公约数，等价于求n 和m%n的最大公约数，用图来表示即不断地用n去填充 m表示的区域，接着赋值n=m%n，m=n 重复上述操作直到m%n==0，则n就是m和n的最大公约数。

AC代码（C语言）

#include<stdio.h>
int gcd(int m,int n){	int t;if(n>m){//令m>nt=n;n=m;m=t;}if(m%n==0) return n;return gcd(n,m%n);
}
int main(){int m,n;scanf("%d%d",&m,&n);int gc=gcd(m,n);int cm=(m/gc)*(n/gc)*gc;printf("%d\n%d\n",gc,cm);return 0;
}