💡题解与思路（带公式）

我们已知公式：

gcd ⁡ ( 𝑎 , 𝑏 ) × lcm ⁡ ( 𝑎 , 𝑏 )

𝑎 × 𝑏 gcd(a,b)×lcm(a,b)=a×b 设：

𝑎

𝑔 × 𝑥 , 𝑏

𝑔 × 𝑦 a=g×x,b=g×y 那么：

$\gcd(a, b) = g \Rightarrow \gcd(x, y) = 1$

$\operatorname{lcm}(a, b) = l \Rightarrow \operatorname{lcm}(x, y) = \frac{l}{g}$

因为 $\gcd(a,b) \cdot \operatorname{lcm}(a,b) = a \cdot b = g^2 \cdot x \cdot y$

所以我们的问题转化为：

✨数学转换：

设 $m = \frac{l}{g}$

寻找所有满足 $\gcd(x, y) = 1$ 且 $x \cdot y = m$ 的数对 $(x, y)$

然后将最小化 $a + b = g \cdot (x + y)$

✅求解步骤：

令 $m = \frac{l}{g}$；

枚举 $x$ 的所有因子 $d$，判断是否满足：

$d \cdot \frac{m}{d} = m$

$\gcd(d, \frac{m}{d}) = 1$

选择使得 $d + \frac{m}{d}$ 最小的因子对；

输出结果为 $g \cdot d$ 和 $g \cdot \frac{m}{d}$（按升序）。

📌注意事项：

答案需使用大整数，防止溢出；

输出为升序；

如果有多组数对满足条件，选择使 $a + b$ 最小的一组；

可使用 __int128 或 __int64 进行处理（根据语言支持）； 代码实现

import java.util.Scanner;
import java.math.*;
 
public class Main{
	public static void main(String[] args){
		Scanner cin = new Scanner(System.in);
		long a, b, x, y;
		while(cin.hasNext()){
			a = cin.nextLong();
			b = cin.nextLong();
			x = y = 0;
			b /= a;
			for(long i = (long)Math.sqrt(b); i > 0; i --){
				if(b%i == 0&&gcd(i, b/i) == 1){
					x = i*a; y = b/i*a; break;
				}
			}
			System.out.println(x+" "+y);
		}
	}
	public static long gcd(long a, long b){
		if(a<b){
			long t =a; a = b; b = t;
		}
		if(b == 0) return a;
		else return gcd(b, a%b);
	}
}