codeforces163D

Large Refrigerator

CodeForces - 163D

给定一个长方体的体积V，求出这个长方体的最小表面积。

输入

第一行有一个整数t (1 ≤ t ≤ 500) — 测试数据的组数。

下面是t组测试数据。每一组表示一个整数V (2 ≤ V ≤ 10¹⁸)，通过分解质因数的形式给出。

设V = p₁^a₁p₂^a₂... p_k^a_k，其中p_i 是不同的素数，a_i是正整指数。

第一行给出一个正整数k — V中不同的质因子的个数。下面k行每行两个数字：p_i和a_i，用空格隔开。每一个p_i都是不同的。所有a_i > 0。

输出

输出t 行，在第i行输出第i-组测试数据的答案，其中包含4个空格隔开的数：最小表面积S和对应的长宽高的长度a，b，c。如果有多个答案，输出任意。长宽高顺序没有规定。

样例

输入

输出

24 2 2 2
70 1 1 17
148 4 6 5

注释

在第一个测试数据中体积V = 2³ = 8，最小表面积可由三边相等的正方体构成。

在第二个测试数据中体积V = 17，该长方体只有一种构成方法。

sol：直接爆搜会T出屎，所以要剪枝，我就XJB剪了一下，先搜a再搜b，强制a<b<c，还有中间如果体积已经超出了就退出，然后就过了

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;

inline ll read()

{

    ll s=;

    bool f=;

    char ch=' ';

    while(!isdigit(ch))

    {

        f|=(ch=='-'); ch=getchar();

    }

    while(isdigit(ch))

    {

        s=(s<<)+(s<<)+(ch^); ch=getchar();

    }

    return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

    if(x<)

    {

        putchar('-'); x=-x;

    }

    if(x<)

    {

        putchar(x+''); return;

    }

    write(x/);

    putchar((x%)+'');

    return;

}

#define W(x) write(x),putchar(' ')

#define Wl(x) write(x),putchar('\n')

const int N=;

const ll inf=0x7fffffffffffffffll;

int T,n,tot=;

struct Node

{

    ll p,a;

    inline bool operator<(const Node &tmp)const

    {

        return p<tmp.p;

    }

}Num[N];

ll P[N],A[N],V,ans,aa,bb,cc;

inline ll Ksm(ll x,ll y)

{

    ll Res=;

    while(y)

    {

        if(y&) Res=1ll*Res*x; x=1ll*x*x; y>>=;

    }

    return Res;

}

inline bool Judge(ll a)

{

    return (1ll*(sqrt(V/a)**a+V/a)<=ans);

}

inline void dfs(int Now,ll a);

inline void dfs1(int Now,ll a,ll b);

inline void dfs(int Now,ll a)

{

    if(a*a*a>V) return;

    if(Now==n+)

    {

        if(Judge(a)) dfs1(,a,);

        return;

    }

    int i;

    ll tmp=Ksm(P[Now],A[Now]);

    for(i=A[Now];i>=;i--)

    {

        A[Now]-=i;

        dfs(Now+,a*tmp);

        A[Now]+=i;

        tmp/=P[Now];

    }

    dfs(Now+,a);

}

inline void dfs1(int Now,ll a,ll b)

{

    if(a*b*b>V) return;

    if(Now==n+)

    {

        ll c=V/a/b,tmp; tmp=a*b+a*c+b*c;

        if(tmp<ans)

        {

            ans=tmp; aa=a; bb=b; cc=c;

        }

        return;

    }

    int i;

    ll tmp=Ksm(P[Now],A[Now]);

    for(i=A[Now];i>=;i--)

    {

        A[Now]-=i;

        dfs1(Now+,a,b*tmp);

        A[Now]+=i;

        tmp/=P[Now];

    }

    dfs1(Now+,a,b);

}

int main()

{

    int i;

    R(T);

    while(T--)

    {

        V=; ans=inf; R(n); tot=;

        for(i=;i<=n;i++)

        {

            R(Num[++tot].p); R(Num[tot].a); V*=Ksm(Num[tot].p,Num[tot].a);

        }

        sort(Num+,Num+tot+);

        for(i=;i<=tot;i++) {P[i]=Num[i].p; A[i]=Num[i].a;}

        dfs(,);

        W(1ll*ans*); W(aa); W(bb); Wl(cc);

    }

    return ;

}

/*

Input

4

1

2 3

1

17 1

3

3 1

2 3

5 1

1

2 2

Output

24 2 2 2

70 1 1 17

148 4 6 5

16 2 2 1

input

3

4

208513 1

2 1

10753058401 1

223 1

4

17469877 1

1283 1

949261 1

47 1

4

313 1

2 1

1546412477693 1

1033 1

output

4493896846822714 446 208513 10753058401

35388330702870 60301 949261 17469877

5130996602278690 626 1033 1546412477693

*/

巴特西

codeforces163D

Large Refrigerator

最新文章

热门文章