java - 整数を入力し、一辺が a と b の長方形を出力し、差が最小になるようにします

Question

誰かがこの問題のアイデアやコードの実装を持っているでしょうか? どうもありがとう！宿題ではありません。

整数を指定して、関数 foo(int area) を記述します。この関数は長方形を返す必要があり、この長方形は a と b の 2 辺の差が最小であり、a*b は面積より大きく、(面積 + 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. 動的計画法を使用して、標準タスクを解決します。2 つの部分の配列を連結するため、すべての部分の総積ができるだけ近くなるはずです。