BZOJ 1263 整数划分(数学+高精度)

我们不妨考虑可以划分为实数的情况，设划分为x份实数，使得总乘积最大。

易得当每一份都相等时乘积最大。即 ans=(n/x)^x. 现在只需要求出这个函数取得最大值的时候x的取值了。

两边取对数，则有ln(ans)=x*ln(n/x). 再两边取导数。可得当x=n/e的时候，每份是e的时候，总乘积最大。

那么现在考虑为整数的情况，由于3最接近e，则尽量将n分成每份为3.

那么现在就可以得出，当n%3==0时，分成n/3份3.

当n%3==1时，分成n/3-1份3和一份4.

当n%3==2时，分成n/3份3和一份2.

再结合高精度乘法即可求出答案。

# include <cstdio>

# include <cstring>

# include <cstdlib>

# include <iostream>

# include <vector>

# include <queue>

# include <stack>

# include <map>

# include <set>

# include <cmath>

# include <algorithm>

using namespace std;

# define lowbit(x) ((x)&(-x))

# define pi 3.1415926535

# define eps 1e-

# define MOD

# define INF

# define mem(a,b) memset(a,b,sizeof(a))

# define FOR(i,a,n) for(int i=a; i<=n; ++i)

# define FO(i,a,n) for(int i=a; i<n; ++i)

# define bug puts("H");

# define lch p<<,l,mid

# define rch p<<|,mid+,r

# define mp make_pair

# define pb push_back

typedef pair<int,int> PII;

typedef vector<int> VI;

# pragma comment(linker, "/STACK:1024000000,1024000000")

typedef long long LL;

int Scan() {

    int res=, flag=;

    char ch;

    if((ch=getchar())=='-') flag=;

    else if(ch>=''&&ch<='') res=ch-'';

    while((ch=getchar())>=''&&ch<='')  res=res*+(ch-'');

    return flag?-res:res;

}

void Out(int a) {

    if(a<) {putchar('-'); a=-a;}

    if(a>=) Out(a/);

    putchar(a%+'');

}

const int N=;

//Code begin...

struct BigInt{

    const static int mod=;

    const static int DLEN=;

    int a[], len;

    BigInt(){mem(a,); len=;}

    BigInt(int v){

        mem(a,); len=;

        do{a[len++]=v%mod; v/=mod;}while(v);

    }

    BigInt operator*(const BigInt &b)const{

        BigInt res;

        FO(i,,len) {

            int up=;

            FO(j,,b.len) {

                int temp=a[i]*b.a[j]+res.a[i+j]+up;

                res.a[i+j]=temp%mod;

                up=temp/mod;

            }

            if (up) res.a[i+b.len]=up;

        }

        res.len=len+b.len;

        while (res.a[res.len-]==&&res.len>) res.len--;

        return res;

    }

    void output(){

        if (len<=) {

            printf("%d",a[len-]);

            for (int i=len-; i>=; --i) printf("%04d",a[i]);

            putchar('\n');

        }

        else {

            int x=a[len-], res=;

            while (x) res++, x/=;

            printf("%d",a[len-]);

            for (int i=len-; i>len--(-res)/; --i) printf("%04d",a[i]);

            if ((-res)%) {

                int t=(-res)%, tmp=a[len--(-res)/];

                FO(i,t,) tmp/=;

                if (t==) printf("%d",tmp);

                else if (t==) printf("%02d",tmp);

                else printf("%03d",tmp);

            }

        }

    }

    int cal_len(){

        int x=a[len-], res=;

        while (x) res++, x/=;

        return res+(len-)*;

    }

};

BigInt ans;

int main ()

{

    int n;

    scanf("%d",&n);

    ans=BigInt();

    while (n>=) ans=ans*BigInt(), n-=;

    if (n==) ans=ans*BigInt();

    else ans=ans*BigInt(n);

    printf("%d\n",ans.cal_len());

    ans.output();

    return ;

}