最接近平方根的因子分解

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}.

英文解析

To minimize $|a-b|$ is to keep $a,b$ as close as possible to $\sqrt{N}$ .

The closest possible pair of all factors to enumerate $a\le \sqrt{1234567890}$ is

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

Therefore,

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