最大公约数与最小公倍数

题目描述

输入两个正整数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,mmodn)\operatorname{gcd}(m, n)=\operatorname{gcd}(n, m \bmod n)gcd(m,n)=gcd(n,mmodn) (不妨设 m>nm>nm>n 且 r=mmodn,r≠0r=m \bmod n, r \neq 0r=mmodn,r=0 )

mmm 可以表示成 m=kn+r(m,n,k,rm=k n+r(m, n, k, rm=kn+r(m,n,k,r 皆为正整数, 且 r 而 r=m−knr=m-k nr=m−kn,两边同时除以 ddd ，可得:
rd=md−knd=h\frac{r}{d}=\frac{m}{d}-\frac{k n}{d}=h dr​=dm​−dkn​=h
由等式右边可知 hhh 为整数（ ddd 是 mmm 和 nnn 的公约数， knk nkn 是 nnn 的整倍数，所以 knd\frac{k n}{d}dkn​ 也应该是整数），所 以我们得出 ddd 也为 mmm 和 nnn 的余数的公约数即 ddd 是 n，mmodnn ， m \bmod nn，mmodn 的公约数
至此，我们得知，如果一个数是两个数的公约数，那么，它也是这两个数的余数和较小数公约数。
假设 ddd 是 (n,mmodn)(n, m \bmod n)(n,mmodn) 的任意一个公约数，则 ddd 是 nnn 的公约数， ddd 是 (m−kn)(m-k n)(m−kn) 的公约数， kkk 是一个整数，
我们假设 n=xd,m−kn=ydn=x d, m-k n=y dn=xd,m−kn=yd 其中 x,yx, yx,y 是正整数，根据上面的推断可得:
m=yd+knm=y d+k n m=yd+kn
两边同时除以 ddd ，得
md=y+knd\frac{m}{d}=y+\frac{k n}{d} dm​=y+dkn​
由已知可得 yyy 为正整数， ddd 是 mmm 的公约数， knd\frac{k n}{d}dkn​ 也肯定是正整数，故得 ddd 为 mmm 的公约数.
因为 ddd 既是 nnn 的公约数又是 mmm 的公约数了，
所以证出 (m,n)(m, n)(m,n) 和 (n,mmodn)(n, m \bmod n)(n,mmodn) 的公约数是一样的，其最大公约数也必然相等。

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

AC代码（C语言）

#include
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;
}