解题思路

$\mathrm{lcm}(a,n-a)=a(n-a)/\gcd(a,n)$ 。奇数 $n$ 时取相邻两半即可（互质）。偶数 $n$ 时从 $n/2$ 向下找到与 $n$ 互质的 $a$ ，此时 $a$ 与 $n-a$ 都尽量接近且 $\gcd(a,n)=1$ 。

复杂度分析

单次询问在与 $n$ 互质的间隔内扫描，总体可在时限内通过。空间复杂度 $O(1)$ 。

调度模块要把额度 $n$ 拆成两份正整数 $a$ 和 $b$ ，满足 $a+b=n$ ，并希望对冲指标 $\mathrm{lcm}(a,b)$ 尽可能大。共有 $t$ 次独立查询，每次给出一个 $n$ 。

请对每次查询输出一组使最小公倍数最大的 $a$ 和 $b$ 。

约束：询问次数不超过 100000， $2 \le n \le 10000000000000$ 。

选择提交后点击「开始AI分析」