gpt4 book ai didi

algorithm - 将一个数分成三部分,并使 lcm(a,b,c) 尽可能小

转载 作者:行者123 更新时间:2023-12-04 12:14:40 25 4
gpt4 key购买 nike

Suppose n be an integer > 2. How do we find 3 positive integers a, b, c, such that n = a+b+c and that their least common multiple, lcm(a,b,c), are as small as possible?

For example, 17 = 2+5+10 and lcm(2,5,10) = 10. However, 17=(1+8+8) and lcm(1,8,8)=8 also is possible. Thus, in this problem, the division of 17 into 1,8,8 is better than 2,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/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com