英文:
Finding min(A+B+C) when N = A*B*C is given
问题
我遇到了这样的问题：
给定正整数 N，找到 min(A+B+C)
其中 A、B、C 也是正整数
且 A*B*C = N.
我已经用 Pollard-Rho 算法因式分解了 N。但由于 A、B、C 都是整数，似乎难以分配质因数。
(为了清晰起见，N <= 1e15)
这个问题是否众所周知？哪种算法最好？
我尝试过：
(贪婪法) 令 A、B、C = 1。
从最大的质因数迭代到最小的质因数，从 A、B、C 中找到最小值，然后将该质因数相乘。
对于 N = 986387345919360 = 2^7 * 3^4 * 5 * 7 * 11 * 17 * 19 * 23 * 29 * 31 * 37，这种方法失败了。
英文:
I've encountered a problem like this:
> given positive integer N, find min(A+B+C)
> when A,B,C are also positive
> integers and A*B*C = N.
I've managed to factorize N with pollard-rho algorithm. But since A, B, C are integers, it seems hard to distribute prime factors.
(for clarity, N <= 1e15)
is this problem well known? What algorithm would be best?
I've tried:
(greedy) Let A, B, C = 1.
iterating from largest prime factor to smallest, find minimum from A, B, C and multiply the prime factor.
This fails for N = 986387345919360 = 2^7 * 3^4 * 5 * 7 * 11 * 17 * 19 * 23 * 29 * 31 * 37
答案1
得分: 1
自己回答因为我解决了它;
我的算法如下：
- 按升序对N的所有因子进行排序。
- 已知N的因子数量不会超过26880。
- 通过列表进行迭代，设A为正在迭代的因子。然后B*C = N/A。
- 由于A是固定的，问题就简化为其自身的一个小版本。
- 计算S = sqrt(N/A)。B和C应尽可能接近S。
- 在步骤1中使用二分搜索在排序的因子列表中找到B = S的下限。如果这个B不能整除S，向后迭代直到B|S。
这个算法的时间复杂度不是O(NlogN)，因为找到B需要迭代，但仍然运行得相当不错。
英文:
Self answering because I solved it;
My algorithm looks like this:
- Sort all divisors of N by ascending order.
- it is known that N's divisor count cannot exceed 26880.
- Iterating through the list, let A be the iterating divisor. Then B*C = N/A.
- since A is fixed, the problem reduces to a small version of itself.
- Compute S = sqrt(N/A). B and C should be close as possible to S.
- Using binary search in the sorted divisor list at step 1, let B = lower bound of S. If this B cannot divide S, iterate backwards until B|S.
This algorithm's time complexity is NOT O(NlogN) because finding B uses iteration, but still runs pretty well.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论