【题解】[SCOI2006] 整数划分 压位高精 LUOGU P4157 -B_Z_B_Y

Main Algorithms ： 压位高精乘法+快速幂 +O2

压位高精快的超乎想象（吸 O2 飞）QWQ

让我们愉悦的学习吧 OvO

题意：将 n 写成若干个正整数之和，并且使这些正整数的乘积最大

主要是将一个序列划分为 k 段（总和为 n），但没有说要不一样，因此好好想想就知道只需将这个序列越平均分越好
，所以相当于 $(n/k)^k$；
实验在持续三分 $n/k$时，会无限接近 $2.71828$（自然对数）-》越平均-》乘积越大
所以要尽量把每一份分成 3 分，就大概这样 $pow（3，x）$，而对于 $x$的取值要有特判。

$Rem=n~mod~3,~(Rem==1)~Rem+=3$
$所以 Rem 的取值为 1,2,4；如果 n~mod~3==1，余数为 1，那么 x-1；Rem=4；$

代码中 $Rem$定义为 $lk$

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define fors(i,a,b) for(int i=(a);i<=(b);++i)
typedef  long long ll;
const int power=9;
const ll base=1e9;
const int maxn=10007;
int lens,lk,x,n;
void write(int x){
    if(x>9) write(x/10);
    putchar(x%10+'0');
    ++lens;
    if(lens==100) exit(0);//在输出判断字符个数
}
struct Bignum//压位高精模板
{
    ll v[maxn];
    Bignum() {
        memset(v,0,sizeof v);
    }
    Bignum(string s){//初始化 string -》Bignum
        memset(v,0,sizeof v);
        int len=s.length();
        v[0]=(len+power-1) / power;
        for(int i=0,t=0,w=0;i<len;w*=10,++i){
            if(i%power == 0)    w=1,++t;
            v[t]+=w*(s[i]-'0');
        }
    }
    int ls(){
        return power*(v[0]-1)+log10(v[v[0]])+1;//返回数的总长度
    }
    void print(){
        write(v[v[0]]);
        for(int i=v[0]-1;i>0;--i){
            for(int k=base/10;v[i]<k;k/=10) write(0);//打印如果不满足 power 位补 0
            if(v[i]) write(v[i]); 
        }
        printf("\n");  
    }
}p,q,ans,tmp;

Bignum operator * (const Bignum &p,const Bignum &q){//高精*高精
    Bignum c;
    c.v[0]=p.v[0]+q.v[0]-1;
    fors(i,1,p.v[0])
    fors(j,1,q.v[0]){
        c.v[i+j-1] += p.v[i]*q.v[j];
        c.v[i+j] += c.v[i+j-1]/base;//base 为压位数，一个空间的数<base
        c.v[i+j-1] %= base;
    }
    if(c.v[ c.v[0]+1 ]) ++c.v[0];
    return c;
}

Bignum zero=Bignum("0");
Bignum one=Bignum("1");

Bignum pows(Bignum a,int b){//高精快速幂
    Bignum res=one;
    while(b){
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}
int main(int argc, char const *argv[])
{
    scanf("%d",&n);
    lk=n%3;
    if(lk==1){
        lk+=3;
        x=n/3-1;
    }
    else x=n/3;
    lk=lk>1 ? lk : 1;
    //lk 的取值为 1,2,4；如果 n%3==1，余数为 1，那么 x-1；lk=4；
    string sa;
    while(lk){
        sa+=(char)(lk%10+'0');
        lk/=10;
    }//因为 Bignum 用的是字符串转的，所以将 lk-》sa;
    ans=pows(Bignum("3"),x)*sa;//*sa 表示乘以那多余的余数；
    write(ans.ls());
    printf("\n");
    lens=0;//从这开始计算输出的字符个数
    ans.print();
    return 0;

}