ICPC国内予選2020 C問題：荷物

問題. 荷物

正整数 $p$ が与えられる。正整数 $w, d, h$ で $p = w \times d \times h$ を満たすもの中で $w + d + h$ の最小値を答えよ。

制約： $1 < p < 10^{15}$

解法．枝刈り探索

枝刈り探索を用いたヒューリスティックな解法を説明します。

初めに、 $p$ の素因数分解を $p = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$ として求めます。今回の問題は複数のテストケースが一度に与えられるので、初めに $32,000,000$ までの素数をエラトステネスの篩で求めて、各テストケースに対してその素数表を用いた素因数分解（自明な分割）を行います。何度も素因数分解を行う場合は予め素数表を求めることによって計算時間が高速になります。

制約 $p = w \times d \times h$ より $w, d, h$ に対して
　・ $w = p_1^{w_1} p_2^{w_2} \cdots p_k^{w_k}$
　・ $d = p_1^{d_1} p_2^{d_2} \cdots p_k^{d_k}$
　・ $h = p_1^{h_1} p_2^{h_2} \cdots p_k^{h_k}$
　・ $\forall i \in \{1, \ldots, k\},$ $0 \le w_i, d_i, h_i \le \alpha_{i}$ かつ $w_i + d_i + h_i = \alpha_{i}$
となる $(w_1, \ldots, w_k), (d_1, \ldots, d_k), (h_1, \ldots, h_k)$ を全探索します。
探索する順番は $w_1, w_2, \ldots, w_k, d_1, d_2, \ldots, d_k$ とします。ただし、 $w_i$ と $d_i$ の値が求まっているときには $h_i = \alpha_i - w_i - d_i$ から $h_i$ も定まります。

高速化として $w \ge d$ かつ $w \ge h$ を満たすように探索をして、探索途中の値 $p_1^{w_1} \ldots p_k^{w_k} + p_1^{d_1} \ldots p_i^{d_i} + p_1^{h_1} \ldots p_i^{h_i}$ が暫定値よりも悪くなるなら枝刈りをして探索を止めます。

計算時間は分かりませんが、素因数の個数より
　 $k \le \frac{\log p}{\log \log p - 1.1714} \le 14.5691...$ 、
　 $\sum_{i = 1}^{k} \alpha_{i} \le \frac{\log p}{log 2} \le 49.8...$
となるので数分以内で解けるのではと予想できます。

計算時間：不明（解析を追記したので下を参考に）

ソースコードを表示

#include <iostream>
#include <vector>
#include <tuple>
#include <numeric>
#include <cmath>

using namespace std;

using ll = long long;

template<class T>
std::vector<T> GetPrimes(const T N) {
    std::vector<bool> is_p(N + 1, true); // 素数表
    std::vector<T> primes;

    is_p[0] = is_p[1] = false;
    for (T i = 2; i <= N; ++i) {
        if (is_p[i]) {
            primes.push_back(i);
            for (T j = i * i; j <= N; j += i)
                is_p[j] = false;
        }
    }
    return primes;
}

template<class T>
struct PrimeFactorization {
    PrimeFactorization() {
        primes = GetPrimes(MAX_N);
    }
    const ll MAX_N = 32'000'000;
    std::vector<T> primes;

    std::vector<std::pair<T, T>> GetPrimeFactorization(T n) {
        std::vector<std::pair<T, T>> pf;
        T m = n;
        for (const T p : primes) {
            if (p * p > n) break;
            if (m % p != 0) continue;
            T cnt = 0;
            while (m % p == 0) { ++cnt; m /= p; }
            pf.emplace_back(std::make_pair(p, cnt));
        }
        if (1 < m) pf.emplace_back(std::make_pair(m, 1));
        return pf;
    }
};

ll ans;
void Solve(const ll a, const int idx_a, const ll b, const int idx_b, const ll c, vector<pair<ll, ll>>& pf) {
    const int size = pf.size();
    if (idx_a >= size && idx_b >= size) {
        ans = std::min(ans, a + b + c);
        return ;
    }

    auto& pf_idx = (idx_a < size) ? pf[idx_a] : pf[idx_b];
    const ll ub = pf_idx.second;
    for (ll p = 0, mul = 1; p <= ub; ++p) {
        pf_idx.second = ub - p;

        if (idx_a < size)  {
            Solve(mul * a, idx_a + 1, b, idx_b, c, pf);
        }
        else {
            const ll mul_c = std::pow(pf_idx.first, pf_idx.second);
            if (a >= mul * b && a >= mul_c * c && a + mul * b + mul_c * c < ans)   // a >= b >= c
                Solve(a, idx_a, mul * b, idx_b + 1, mul_c * c, pf);
        }
        mul *= pf_idx.first;
    }
    pf_idx.second = ub;
}

int main() {
    PrimeFactorization<ll> pf;

    ll n;
    while (cin >> n, n) {
        auto pf_n = pf.GetPrimeFactorization(n);
        ans = std::numeric_limits<ll>::max();
        Solve(1, 0, 1, 0, 1, pf_n);
        std::cout << ans << std::endl;
    }

    return 0;
}

計算時間の見積もり（追記）

$(w_1, \ldots, w_k), (d_1, \ldots, d_k), (h_1, \ldots, h_k)$ が最悪の場合に何通りあるかを求めます。

$k \le 14$ かつ $\sum_{i = 1}^{k} \alpha_{i} \le 49$ なので、最悪の場合の数は各 $1 \le k \le 14$ に対して次の最適化問題の最適値の最大値となります。
　maximize　 $x_1 \times x_2 \times \cdots \times x_{2 k}$
　subject to　 $x_1 + x_2 + \cdots + x_{2 k} = 49$

この最大化問題は多変数の相加相乗平均
　 $\sum_{i = 1}^{2 k} x_i \ge 2 k \sqrt[2 k]{\prod_{i = 1}^{2 k} x_i}$
を用いて
　 $\left(\frac{\sum_{i = 1}^{2 k} x_i}{2 k} \right)^{2 k} \ge \prod_{i = 1}^{2 k} x_i$
と表せられます。制約条件より $\sum_{i = 1}^{2 k} x_i = 49$ なので、上の最大化問題の最大値は
　 $\left(\frac{\sum_{i = 1}^{2 k} x_i}{2 k} \right)^{2 k} = \left(\frac{49}{2 k} \right)^{2 k}$
となります。等号成立条件は $x_1 = x_2 = \cdots = x_{2 k}$ なので $\frac{x}{2 k} = 49$ を満たす自然数 $x$ が存在することが必要ですが大雑把に $x$ は実数として解析をします。
$1 \le k \le 14$ に対して $\left(\frac{49}{2 k} \right)^{2 k}$ の最大値を計算すると約 $1.8 \times 10^{8}$ となります。素因数分解をする計算時間と合わせてもコンテスト中に終わる妥当なアルゴリズムだと思います。
　