数学、构造

钦定 $a \leq b$，注意到最坏情况下 $a=1,b=n-1$，可能更优的情况下 $b=k \times a\ (k \geq 1)$，此时有 $\operatorname{lcm}(a,b)=b$。由 $a+b=n$ 得 $n=(k+1) \times a$，枚举 $n$ 的因数 $(k+1) \in [2,\lfloor \sqrt n \rfloor]$，答案为最大的 $a=n \div (k+1)$ 和对应的最小的 $b$，找到最小的正整数 $k$ 可以求解。没有在范围内找到 $k$ 当且仅当 $n$ 是质数，此时 $a=1,k=b=n-1$，时间复杂度 $O(\sqrt n)$。