【Luogu】B3634 最大公约数和最小公倍数

（附：下文中 ( a , b ) (a,b) (a,b) 表示 a a a 与 b b b 的最大公因数， [ a , b ] [a,b] [a,b] 表示 a a a 与 b b b 的最小公倍数。）

我们可以用辗转相除法模拟求 ( a , b ) (a,b) (a,b) 的过程。

我们也可以直接使用 C++ 的函数 __gcd() 来求出 ( a , b ) (a,b) (a,b)。

至于 [ a , b ] [a,b] [a,b]，我们可以直接输出 a*b/__gcd(a,b)。

以下是证明：

令 x = ( a , b ) , y = [ a , b ] x=(a,b),y=[a,b] x=(a,b),y=[a,b]，

则 a = p x , b = q x , p ⊥ q a=px,b=qx,p bot q a=px,b=qx,p⊥q，

故 y = p × q × x y=ptimes q times x y=p×q×x，

因此 x y = x ( p q x ) = ( p x ) ( q x ) = a b , a b = ( a , b ) × [ a , b ] xy=x(pqx)=(px)(qx)=ab,ab=(a,b)times[a,b] xy=x(pqx)=(px)(qx)=ab,ab=(a,b)×[a,b]。

证毕。

AC Code：

#include
using namespace std;

int main()
{
	long long a,b;//题目不保证 a*b 不超出 int，故使用 long long
	cin>>a>>b;
	cout<<__gcd(a,b)<<' '<