爆搜题。
由题列出以下方程组：
\[ \begin{cases}
abc=V\\
\frac{S}{2}=ab+bc+ac
\end{cases}
\]
化简得：
\[ \frac{S}{2}=a(b+c)+\frac{V}{a}
\]
又由基本不等式 \(a+b\geq 2\sqrt{ab}\) 得：
\[ \frac{S}{2}\geq 2a\sqrt{bc}+\frac{V}{a}\\
\]
即：
\[ \frac{S}{2}\geq 2a\sqrt{\frac{V}{a}}+\frac{V}{a}\\
\]
现在我们来考虑搜索的问题。
不妨设 \(a\leq b\leq c\)。
显然 \(a\leq \sqrt[3]{V},b\leq \sqrt{\frac{V}{a}}\)。
搜索的 \(S\)，必定呈一个单调不上升趋势，那么我们进行最优性剪枝，当 \(\frac{S}{2}\geq 2a\sqrt{\frac{V}{a}}+\frac{V}{a}\) 时，直接返回。
注意，由于本题给的是质因数乘积形式，我们需要在输入时乘起来。
复杂度玄学，但在 CF 数据下可过。
代码如下：
#define int long long
constexpr int N = 105, inf = LLONG_MAX;
namespace Jelly {
int k, p[N], cnt[N], v, ans, a, b, c;
void B(int try_a, int depth, int sum) {
if (square(sum) > v / try_a) return ;
if (depth > k) {
int try_c = v / try_a / sum;
if (try_c * sum + try_a * sum + try_a * try_c < ans) {
ans = try_c * sum + try_a * sum + try_a * try_c;
a = try_a, b = sum, c = try_c;
}
return ;
}
if (cnt[depth]) -- cnt[depth], B(try_a, depth, sum * p[depth]), ++ cnt[depth];
B(try_a, depth + 1, sum);
}
void A(int depth, int sum) {
if (cube(sum) > v) return ;
if (depth > k) {
if (sum * 2 * sqrt(v / sum) + v / sum < ans) B(sum, 1, 1);
return ;
}
if (cnt[depth]) -- cnt[depth], A(depth, sum * p[depth]), ++ cnt[depth];
A(depth + 1, sum);
}
int main() {
Read(k), v = 1;
REP(i, 1, k) {
Read(p[i], cnt[i]);
REP(j, 1, cnt[i]) v *= p[i];
}
ans = inf, A(1, 1);
Writeln(ans * 2, ' ', a, ' ', b, ' ', c);
return 0;
}
}
signed main() {
int T;
Read(T);
while (T --) Jelly::main();
return 0;
}