最大公约数和最小公倍数(gcdlcm.cpp)

问题描述

最大公约数(Greatest Common Divisor，简写为GCD)：如果有一个自然数a能被自然数b整除(也称b能整除a，记作b|a)，则称a为b的倍数，b为a的约数。两个自然数公共的约数，叫做这两个自然数的公约数。公约数中最大的一个公约数，称为这两个自然数的最大公约数。最小公倍数(Least Common Multiple，缩写LCM)：对于两个整数来说，最小公倍数是指这两个数公共的倍数中最小的一个。例如： 在12和16中，4就是12和16的最大公约数。12和16的最小公倍数是48。

早在公元前300年左右，欧几里得就在他的著作《几何原本》中给出了求最小公倍数的高效方法——辗转相除法。辗转相除法使用到的原理很聪明也很简单，假设用GCD(x, y)表示x，y的最大公约数，取k = x div y，b = x mod y，则x = ky + b，如果一个数能够同时整除x和y，则必能同时整除b和y；而能够同时整除b和y的数也必能同时整除x和y，即x和y的公约数与b和y的公约数是相同的，其最大公约数当然也相同，则当y<>0时有GCD(x, y)= GCD(y, x mod y)，如此便可把原问题转化为求两个更小数的最大公约数，直到其中一个数为0，剩下的另外一个数就是两者的最大公约数。以求288和123的最大公约数为例，操作如下： 　　

288 mod 123=42 　　123 mod 42=39 　　42 mod 39=3 　　39 mod 3=0 　　

所以3就是288和123的最大公约数。

计算最小公倍数时，通常会借助最大公约数来辅助计算。可以证明两个自然数的乘积等于它们的最大公约数和最小公倍数的乘积，即a*b=GCD(a,b)*LCM(a,b)。如12*16=192= GCD(12,16)*LCM(12,16)=4*48。

编一个程序对于输入的两个自然数a,b，求它们的最大公约数和最小公倍数。

输入格式

输入数据仅有一行包含两个用空格隔开的正整数a,b，范围不超过长整型longint。

输出格式

输出数据仅有一行包含两个整数，表示要求的最大公约数和最小公倍数。两数之间严格用一个空格隔开，行末没有多余的空格。

样例输入

12 16

样例输出

4 48