Suppose
n
be an integer> 2
. How do we find3
positive integersa, b, c,
such thatn = a+b+c
and that their least common multiple,lcm(a,b,c)
, are as small as possible?For example,
17 = 2+5+10
andlcm(2,5,10) = 10
. However,17=(1+8+8)
andlcm(1,8,8)=8
also is possible. Thus, in this problem, the division of17
into1,8,8
is better than2,5,10
.
2 < n < 2^31
我不知道,因为这个数字可能会上升到
2^31
.我已经知道如果
n%3=0
然后 a=b=c=n/3
,但我不知道该怎么做 n%3!=0
.
最佳答案
不失一般性假设 a ≥ b ≥ c。通过平均参数,a ≥ n/3。如果 lcm(a, b, c) < 2n/3,那么由于 a 整除 lcm(a, b, c),我们必定有 lcm(a, b, c) = a,并且 b 和 c 整除 a。
如果 n 是 2 的幂,则最优解为 n/2、n/4、n/4。证明:引用的解是有效的,所以 lcm(a, b, c) ≤ n/2。由于 n/2 < 2n/3,因此 b 和 c 除 a ≤ n/2。因此,a 必须是偶数,b 和 c 必须都是奇数或都是偶数。如果 b 和 c 都是奇数,则 a/2 ≥ b ≥ c,因此 a + b + c = n 仅当 b = c = a/2 = n/4 时。如果 b 和 c 都是偶数,那么我们将所有内容除以 2 并通过归纳进行论证。
如果 n 不是 2 的幂,则令其最小奇素数除数为 p(使用 Pollard's rho 或筛选素数至 √231 并尝试除法求 p);最优解是 (n/p) (p-1)/2, (n/p) (p-1)/2, n/p。证明:引用的解是有效的,所以 lcm(a, b, c) ≤ (n/p) (p−1)/2。由于 (n/p) (p-1)/2 < 2n/3,因此 b 和 c 可除 a ≤ (n/p) (p-1)/2。我们必须有 b = a,否则 a/2 ≥ b ≥ c 将意味着 n ≤ 2a ≤ 2 (n/p) (p−1)/2 = n (1 − 1/p),这是错误的。因此,该解具有 (n - c)/2, (n - c)/2, c 的形式。最优解取 c 为与 n 具有相同奇偶性的 n 的最大自因数,即 c = n/p。
关于algorithm - 将一个数分成三部分,并使 lcm(a,b,c) 尽可能小,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/69413480/