自动搬运

查看原文

来自洛谷，原作者为

	x1489631649 这个家伙很懒，什么也没有留下

搬运于2025-08-24 23:01:56，当前版本为作者最后更新于2024-08-11 19:50:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

输入

多组数据，每组数据两个整数 $x,y(1 \le x,y \le 10^9)$。

输出

最小公倍数除以最大公因数开根号然后找到两个数 $a$ 与 $b$ ，将 $b$ 的开根号在乘 $a$ 等于那个数，且使得 $a \times b$ 的积最大。

分析

1. 首先我们将等式两边同时平方可得最小公倍数除以最大公因数等于 $a^2 \times b$。
2. 转移使得 $a \times b$ 等于最小公倍数除以最大公因数与 $a$ 的乘积。由于最小公倍数和最大公因数已经确定，所以只需要让 $a$ 尽量小，而 $a$ 的最小值只能是 $1$。

实现

我们可以使用系统自带的函数 $\gcd$ 来进行求值然后再用最小公倍数乘最大公因数等于两个数的积来求出最小公倍数。

Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
	unsigned long long t,x,y,flag;
	cin>>t;
	while(t--)
	{
		cin>>x>>y;
		if(x>y)
			swap(x,y);
		cout<<"1 "<<(x*y/__gcd(x,y))/__gcd(x,y)<<endl;
	}
} 

时间复杂度

时间复杂度为 $O(t\log V)$，其中 $V$ 是值域，显然可以通过。