关于 gcd 小结论

输入两个整数 $n, m$，要求找到一组 $x, y$，使得 $x + y = n$ 且 $lcm(x, y) = m$，输出 $x, y$。

考虑最暴力的做法，枚举 $x$，暴力计算，时间复杂度 $O(n\log n)$。

转化一下条件，$\gcd(x, y) = \frac{x\times y}{lcm(x, y)}$，由于 $x + y = n$，即 $y = n - x$，那么有 $\gcd(x, n - x) = \frac{x \times y}{m}$。

结合辗转相除法 $\gcd(x, n - x) = \gcd(x, n)$，所以我们只需枚举 $n$ 的因数作为最大公因数，然后相当于列了个韦达定理，解一元二次方程即可。

时间复杂度 $O(\sqrt{n})$。

但是仍然不够优秀，更进一步不难发现，$\gcd(x, y) = \gcd(n, m)$。

以下是证明：

设 $\gcd(x, y) = k$，令 $x = ak, y = bk$，则有 $\gcd(a, b) = 1$，即 $\gcd(a + b, ab) = 1$。

这时，$n = x + y = (a + b)k$，$m = lcm(x, y) = abk$，则 $\gcd(n, m) = \gcd((a+b)k, abk) = k$。

然后就可以愉快的 $O(1)$ 解决问题啦。