最接近平方根的因子分解

Smallest Factorizaiton

专题: Brainteaser / 脑筋急转弯
难度: L4
来源: QuantQuestion

题目详情

数 $1234567890$ 不是质数，因此可以写成 $ab$ （ $a,b$ 为正整数）。

求 $a^*+b^*$ ，其中 $a^*b^*=1234567890$ ，且对任意其它满足 $ab=1234567890$ 的因子对，都有

|a-b|\ge |a^*-b^*|.

提示：可考虑质因数分解。

The number $1234567890$ is not prime, so it can be written in the form $ab$ for two positive integers $a$ and $b$ . Find $a^* + b^*$ , where $a^*$ and $b^*$ satisfy $a^*b^* = 1234567890$ and for any other pair $(a,b)$ such that $ab = 1234567890$ , $|a-b| \geq |a^* - b^*|$ . It may be helpful to consider the prime factorization.

解析

要使 $|a-b|$ 最小，相当于让 $a,b$ 尽量接近 $\sqrt{N}$ 。

枚举 $a\le \sqrt{1234567890}$ 的所有因子可得最接近的一对为

(a^*,b^*)=(34227,\ 36070).

因此

\boxed{a^*+b^*=70297}.