java - 输入一个整数，输出一个有边a和b的矩形，差应该是最小的

Question

有人可以有这个问题的想法或代码实现吗？非常感谢！这不是家庭作业。

给定一个整数，写一个函数 foo(int area)，这个函数应该返回一个矩形，这个矩形在 a 和 b 两侧的差最小，而且 a*b 必须大于 area 并且小于等于 (面积 + 2)。

Answer 1

好的，如果你没有大面积（如果输入“int”那么是的），复杂度为 O(sqrt(n)) 的解决方案对你来说就足够了。然后你可以使用愚蠢的解决方案。

#include "math.h"

void foo(int area)
{
    long a = (long)sqrt(area + 2);
    while ((area + 1)  % a != 0 && (area + 2) % a != 0) a--;
    long total_area = ((area + 1) % a == 0) ? (area + 1) : (area + 2);
    long b = total_area / a;
    printf("%ld = %ld X %ld", total_area, a, b);
}

此任务的复杂度为 O(N^(1/2))。即使对于长类型，这也足够了。如果您要长期寻找解决方案。然后你需要使用更复杂的算法：

1. 使用快速分解方法得到所有素数除数的数组。
2. 使用动态规划解决标准任务。两部分的连续数组，因此所有部分的总乘积应尽可能接近。