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;

}
分类: 文章

B_Z_B_Y

虽然也包含些许残酷 , 时间毕竟对任何人都很温柔-。---2018 NOIP 退役人士

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *