[BZOJ1263/Luogu4157][SCOI2006]整数划分

题目链接：

BZOJ1263

Luogu4157

是严谨的数学结论题！！一眼出结论，秒了

首先，若把\(n\)分成\(m\)个数，显然越平均乘积越大（小学奥数可能用不等式证明？）

若分的\(m\)个数（实数）为\(x\)，然后就有答案方程\(f(x)=x^{\frac nx}=(x^{\frac 1x})^n\)

因为方程\(f'(x)=x^{\frac 1x}\)当\(x\)取\(e\)时最大

（似乎是某年\(PKUSC\)数学题？网上应该有详细证明，用的导数？我不会不证明了，反正很显然，取值发现答案在\(2\sim 3\)之间就猜出来了，实在不行可以借助计算机画图Geogebra）

又因为这题要取整数，那么就要分成尽可能多的\(2\)和\(3\)（在\(e\)附近的正整数）。

那么接着怎么做呢？枚举\(2\)的个数？

其实\(2\)的个数取值只可能是\(\{0,1,2\}\)其中一个，因为\(2+2+2=3+3,2^3<3^2\)，所以有\(3\)个\(2\)就可以换成\(2\)个\(3\)。

然后套高精度即可。

#include <cstdio>

int n;
struct Big
{
    int s[10005],l;
    inline void operator*=(const int x)
    {
        for(int i=l;i>=1;--i)
            s[i+1]+=(s[i]*=x)/10,s[i]%=10;
        for(int i=1;i<=l;++i)
            s[i+1]+=s[i]/10,s[i]%=10;
        if(s[l+1])++l;
    }
}Ans;

int main()
{
    scanf("%d",&n);
    Ans.s[Ans.l=1]=1;
    for(int i=0;i<=2;++i)
        if((n-i*2)%3==0)//可以取i个2
        {
            for(int j=(n-i*2)/3;j;--j)Ans*=3;
            for(int j=i;j;--j)Ans*=2;
        }
    printf("%d\n",Ans.l);
    for(int i=Ans.l;i>=1&&Ans.l-i<100;--i)printf("%d",Ans.s[i]);
    putchar('\n');
    return 0;
}

[BZOJ1263/Luogu4157][SCOI2006]整数划分

原文：https://www.cnblogs.com/LanrTabe/p/10211480.html