H. GSS and Simple Math Problem 高精度乘法模板

链接：https://www.nowcoder.com/acm/contest/104/G
来源：牛客网

题目描述

Given n positive integers , your task is to calculate the product of these integers, The answer is less than

题解：直接python高精度

坑：c++高精度会T

紫书上的高精度乘法改不来

t = int(input())

p=1

for i in range(t):

    s = int(input())

    p=p*s

print (p)

附：紫书上的高精度乘法：

#include<bits/stdc++.h>

#define lson (rt<<1)

#define rson (rt<<1|1)

#define mp make_pair

#define fi first

#define se second

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;

const int MAXN=;

const int MOD=(int)1e9+;

struct BigInt{

    const static int Base=(int)1e9;

    const static int Len=;

    vector<int>a;

    BigInt(){a={};}

    BigInt(const char *str,const int &l,const int &r){

        for(int i=r-Len+;;i-=Len){

            int tmp=;

            if(i<l){

                for(int j=l;j<i+Len;j++)tmp=tmp*+str[j]-'';

                a.push_back(tmp);

                break;

            }

            for(int j=i;j<i+Len;j++)tmp=tmp*+str[j]-'';

            a.push_back(tmp);

        }

        while(a.back()==&&a.size()>)a.pop_back();

    }

    BigInt operator *(const BigInt &b)const{

        BigInt res;

        res.a.resize(a.size()+b.a.size());

        for(int i=;i<(int)a.size();i++){

            int up=;

            for(int j=;j<(int)b.a.size();j++){

                ll tmp=1ll*a[i]*b.a[j]+res.a[i+j]+up;

                res.a[i+j]=tmp%Base;

                up=tmp/Base;

            }

            if(up!=)res.a[i+(int)b.a.size()]=up;

        }

        while(res.a.back()==&&res.a.size()>)res.a.pop_back();

        return res;

    }

    void display(){

        printf("%d",a.back());

        for(int i=(int)a.size()-;i>=;i--)printf("%09d",a[i]);

    }

}ans;

char str[];

int main()

{

    int n;

    scanf("%d",&n);

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

        scanf("%s",str);

        if(i==)ans=BigInt(str,,strlen(str)-);

        else {

            ans=ans*BigInt(str,,strlen(str)-);

        }

    }

    ans.display();

    return ;

}

/*

20 1

12345678912345678912

*/

以及某丧心病狂的高精度

#include <bits/stdc++.h>

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

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

#define MP make_pair

#define pb push_back

#define fi first

#define se second

#define sz(x) (int)x.size()

#define all(x) x.begin(),x.end()

using namespace std;

#define _GLIBCXX_PERMIT_BACKWARD_HASH

#include <ext/hash_map>

using namespace __gnu_cxx;

struct str_hash{size_t operator()(const string& str)const{return __stl_hash_string(str.c_str());}};

typedef long long ll;

typedef unsigned long long ull;

#define PII pair<int,int>

#define PLL pair<ll,ll>

#define PDD pair<double,double>

const int INF=0x3f3f3f3f;

const ll LLINF=0x3f3f3f3f3f3f3f3f;

const double PI=acos(-1.0);

const double eps=1e-;

const int MAX=2e6+;

const ll mod=1e9+;

const int DIGIT=;

const int DEPTH=;

const int MAXN=;

typedef ll bignum_t[MAXN+];

ll read(bignum_t a,istream&is=cin)

{

    char buf[MAXN*DIGIT+],ch;

    ll i,j;

    memset((void*)a,,sizeof(bignum_t));

    if(!(is>>buf))return ;

    for(a[]=strlen(buf),i=a[]/-;i>=;i--)

    ch=buf[i],buf[i]=buf[a[]--i],buf[a[]--i]=ch;

    for(a[]=(a[]+DIGIT-)/DIGIT,j=strlen(buf);j<a[]*DIGIT;buf[j++]='');

    for(i=;i<=a[];i++)

    for(a[i]=,j=;j<DIGIT;j++)

    a[i]=a[i]*+buf[i*DIGIT--j]-'';

    for(;!a[a[]]&&a[]>;a[]--);

    return ;

}

void write(const bignum_t a,ostream&os=cout)

{

    ll i,j ;

    for(os<<a[i=a[]],i--;i;i--)

    os<<setw(DIGIT)<<setfill('')<<a[i];

}

ll comp(const bignum_t a,const bignum_t b)

{

    ll i ;

    if(a[]!=b[]) return a[]-b[];

    for(i=a[];i;i--)

    if(a[i]!=b[i])

    return a[i]-b[i];

    return  ;

}

ll comp(const bignum_t a,const ll b)

{

    ll c[]={};

    for(c[]=b;c[c[]]>=DEPTH;c[c[]+]=c[c[]]/DEPTH,c[c[]]%=DEPTH,c[]++);

    return comp(a,c);

}

ll comp(const bignum_t a,const ll c,const ll d,const bignum_t b)

{

    ll i,t=,O=-DEPTH*;

    if(b[]-a[]<d&&c)

    return  ;

    for(i=b[];i>d;i--)

    {

        t=t*DEPTH+a[i-d]*c-b[i];

        if(t>)return ;

        if(t<O)return ;

    }

    for(i=d;i;i--)

    {

        t=t*DEPTH-b[i];

        if(t>)return ;

        if(t<O)return ;

    }

    return t> ;

}

void add(bignum_t a,const bignum_t b)

{

    ll i ;

    for(i=;i<=b[];i++)

    if((a[i]+=b[i])>=DEPTH)

    a[i]-=DEPTH,a[i+]++;

    if(b[]>=a[])

    a[]=b[];

    else

    for(;a[i]>=DEPTH&&i<a[];a[i]-=DEPTH,i++,a[i]++);

    a[]+=(a[a[]+]>);

}

void add(bignum_t a,const ll b)

{

    ll i=;

    for(a[]+=b;a[i]>=DEPTH&&i<a[];a[i+]+=a[i]/DEPTH,a[i]%=DEPTH,i++);

    for(;a[a[]]>=DEPTH;a[a[]+]=a[a[]]/DEPTH,a[a[]]%=DEPTH,a[]++);

}

void sub(bignum_t a,const bignum_t b)

{

    ll i;

    for(i=;i<=b[];i++)

    if((a[i]-=b[i])<)

    a[i+]--,a[i]+=DEPTH;

    for(;a[i]<;a[i]+=DEPTH,i++,a[i]--);

    for(;!a[a[]]&&a[]>;a[]--);

}

void sub(bignum_t a,const ll b)

{

    ll i=;

    for(a[]-=b;a[i]<;a[i+]+=(a[i]-DEPTH+)/DEPTH,a[i]-=(a[i]-DEPTH+)/DEPTH*DEPTH,i++);

    for(;!a[a[]]&&a[]>;a[]--);

}

void sub(bignum_t a,const bignum_t b,const ll c,const ll d)

{

    ll i,O=b[]+d;

    for(i=+d;i<=O;i++)

    if((a[i]-=b[i-d]*c)<)

    a[i+]+=(a[i]-DEPTH+)/DEPTH,a[i]-=(a[i]-DEPTH+)/DEPTH*DEPTH ;

    for(;a[i]<;a[i+]+=(a[i]-DEPTH+)/DEPTH,a[i]-=(a[i]-DEPTH+)/DEPTH*DEPTH,i++);

    for(;!a[a[]]&&a[]>;a[]--);

}

void mul(bignum_t c,const bignum_t a,const bignum_t b)

{

    ll i,j;

    memset((void*)c,,sizeof(bignum_t));

    for(c[]=a[]+b[]-,i=;i<=a[];i++)

    for(j=;j<=b[];j++)

    if((c[i+j-]+=a[i]*b[j])>=DEPTH)

    c[i+j]+=c[i+j-]/DEPTH,c[i+j-]%=DEPTH;

    for(c[]+=(c[c[]+]>);!c[c[]]&&c[]>;c[]--);

}

void mul(bignum_t a,const ll b)

{

    ll i;

    for(a[]*=b,i=;i<=a[];i++)

    {

        a[i]*=b ;

        if(a[i-]>=DEPTH)

        a[i]+=a[i-]/DEPTH,a[i-]%=DEPTH;

    }

    for(;a[a[]]>=DEPTH;a[a[]+]=a[a[]]/DEPTH,a[a[]]%=DEPTH,a[]++);

    for(;!a[a[]]&&a[]>;a[]--);

}

void mul(bignum_t b,const bignum_t a,const ll c,const ll d)

{

    ll i;

    memset((void*)b,,sizeof(bignum_t));

    for(b[]=a[]+d,i=d+;i<=b[];i++)

    if((b[i]+=a[i-d]*c)>=DEPTH)

    b[i+]+=b[i]/DEPTH,b[i]%=DEPTH ;

    for(;b[b[]+];b[]++,b[b[]+]=b[b[]]/DEPTH,b[b[]]%=DEPTH);

    for(;!b[b[]]&&b[]>;b[]--);

}

void div(bignum_t c,bignum_t a,const bignum_t b)

{

    ll h,l,m,i;

    memset((void*)c,,sizeof(bignum_t));

    c[]=(b[]<a[]+)?(a[]-b[]+): ;

    for(i=c[];i;sub(a,b,c[i]=m,i-),i--)

    for(h=DEPTH-,l=,m=(h+l+)>>;h>l;m=(h+l+)>>)

    if(comp(b,m,i-,a))h=m-;

    else l=m;

    for(;!c[c[]]&&c[]>;c[]--);

    c[]=c[]>?c[]:;

}

void div(bignum_t a,const ll b,ll&c)

{

    ll i;

    for(c=,i=a[];i;c=c*DEPTH+a[i],a[i]=c/b,c%=b,i--);

    for(;!a[a[]]&&a[]>;a[]--);

}

void sqrt(bignum_t b,bignum_t a)

{

    ll h,l,m,i;

    memset((void*)b,,sizeof(bignum_t));

    for(i=b[]=(a[]+)>>;i;sub(a,b,m,i-),b[i]+=m,i--)

    for(h=DEPTH-,l=,b[i]=m=(h+l+)>>;h>l;b[i]=m=(h+l+)>>)

    if(comp(b,m,i-,a))h=m-;

    else l=m;

    for(;!b[b[]]&&b[]>;b[]--);

    for(i=;i<=b[];b[i++]>>=);

}

ll length(const bignum_t a)

{

    ll t,ret;

    for(ret=(a[]-)*DIGIT,t=a[a[]];t;t/=,ret++);

    return ret>?ret:;

}

ll digit(const bignum_t a,const ll b)

{

    ll i,ret;

    for(ret=a[(b-)/DIGIT+],i=(b-)%DIGIT;i;ret/=,i--);

    return ret%;

}

ll zeronum(const bignum_t a)

{

    ll ret,t;

    for(ret=;!a[ret+];ret++);

    for(t=a[ret+],ret*=DIGIT;!(t%);t/=,ret++);

    return ret;

}

void comp(ll*a,const ll l,const ll h,const ll d)

{

    ll i,j,t;

    for(i=l;i<=h;i++)

    for(t=i,j=;t>;j++)

    while(!(t%j))

    a[j]+=d,t/=j;

}

void convert(ll*a,const ll h,bignum_t b)

{

    ll i,j,t=;

    memset(b,,sizeof(bignum_t));

    for(b[]=b[]=,i=;i<=h;i++)

    if(a[i])

    for(j=a[i];j;t*=i,j--)

    if(t*i>DEPTH)

    mul(b,t),t=;

    mul(b,t);

}

#define SGN(x) ((x)>0?1:((x)<0?-1:0))

#define ABS(x) ((x)>0?(x):-(x))

ll read(bignum_t a,ll&sgn,istream&is=cin)

{

    char str[MAXN*DIGIT+],ch,*buf;

    ll i,j;

    memset((void*)a,,sizeof(bignum_t));

    if(!(is>>str))return ;

    buf=str,sgn=;

    if(*buf=='-')sgn=-,buf++;

    for(a[]=strlen(buf),i=a[]/-;i>=;i--)

    ch=buf[i],buf[i]=buf[a[]--i],buf[a[]--i]=ch ;

    for(a[]=(a[]+DIGIT-)/DIGIT,j=strlen(buf);j<a[]*DIGIT;buf[j++]='');

    for(i=;i<=a[];i++)

    for(a[i]=,j=;j<DIGIT;j++)

    a[i]=a[i]*+buf[i*DIGIT--j]-'';

    for(;!a[a[]]&&a[]>;a[]--);

    if(a[]==&&!a[])sgn=;

    return ;

}

struct bigint

{

    bignum_t num;

    ll sgn;

    bigint(ll v){*this = v;}

    inline bigint()

    {

        memset(num,,sizeof(bignum_t));

        num[]=;

        sgn=;

    }

    inline ll operator!()

    {

        return num[]==&&!num[];

    }

    inline bigint&operator=(const bigint&a)

    {

        memcpy(num,a.num,sizeof(bignum_t));

        sgn=a.sgn;

        return*this;

    }

    inline bigint&operator=(const ll a)

    {

        memset(num,,sizeof(bignum_t));

        num[]=;

        sgn=SGN (a);

        add(num,sgn*a);

        return*this;

    }

    inline bigint&operator+=(const bigint&a)

    {

        if(sgn==a.sgn)add(num,a.num);

        else if(sgn&&a.sgn)

        {

            ll ret=comp(num,a.num);

            if(ret>)sub(num,a.num);

            else if(ret<)

            {

                bignum_t t;

                memcpy(t,num,sizeof(bignum_t));

                memcpy(num,a.num,sizeof(bignum_t));

                sub (num,t);

                sgn=a.sgn;

            }

            else memset(num,,sizeof(bignum_t)),num[]=,sgn=;

        }

        else if(!sgn) memcpy(num,a.num,sizeof(bignum_t)),sgn=a.sgn;

        return*this;

    }

    inline bigint&operator+=(const ll a)

    {

        if(sgn*a>)add(num,ABS(a));

        else if(sgn&&a)

        {

            ll  ret=comp(num,ABS(a));

            if(ret>)sub(num,ABS(a));

            else if(ret<)

            {

                bignum_t t;

                memcpy(t,num,sizeof(bignum_t));

                memset(num,,sizeof(bignum_t));

                num[]=;

                add(num,ABS (a));

                sgn=-sgn;

                sub(num,t);

            }

            else memset(num,,sizeof(bignum_t)),num[]=,sgn= ;

        }

        else if(!sgn) sgn=SGN(a),add(num,ABS(a));

        return*this;

    }

    inline bigint operator+(const bigint&a)

    {

        bigint ret;

        memcpy(ret.num,num,sizeof(bignum_t));

        ret.sgn=sgn;

        ret+=a;

        return ret;

    }

    inline bigint operator+(const ll a)

    {

        bigint ret;

        memcpy(ret.num,num,sizeof (bignum_t));

        ret.sgn=sgn;

        ret+=a;

        return ret;

    }

    inline bigint&operator-=(const bigint&a)

    {

        if(sgn*a.sgn<)add(num,a.num);

        else if(sgn&&a.sgn)

        {

            ll ret=comp(num,a.num);

            if(ret>)sub(num,a.num);

            else if(ret<)

            {

                bignum_t t;

                memcpy(t,num,sizeof(bignum_t));

                memcpy(num,a.num,sizeof(bignum_t));

                sub(num,t);

                sgn=-sgn;

            }

            else memset(num,,sizeof(bignum_t)),num[]=,sgn=;

        }

        else if(!sgn)add(num,a.num),sgn=-a.sgn ;

        return*this ;

    }

    inline bigint&operator-=(const ll a)

    {

        if(sgn*a<)add(num,ABS(a));

        else if(sgn&&a)

        {

            ll ret=comp(num,ABS(a));

            if(ret>)sub(num,ABS(a));

            else if(ret<)

            {

                bignum_t t;

                memcpy(t,num,sizeof(bignum_t));

                memset(num,,sizeof(bignum_t));

                num[]=;

                add(num,ABS(a));

                sub(num,t);

                sgn=-sgn;

            }

            else memset(num,,sizeof(bignum_t)),num[]=,sgn=;

        }

        else if(!sgn)sgn=-SGN(a),add(num,ABS(a));

        return*this ;

    }

    inline bigint operator-(const bigint&a)

    {

        bigint ret;

        memcpy(ret.num,num,sizeof(bignum_t));

        ret.sgn=sgn;

        ret-=a;

        return ret;

    }

    inline bigint operator-(const ll a)

    {

        bigint ret;

        memcpy(ret.num,num,sizeof(bignum_t));

        ret.sgn=sgn;

        ret-=a;

        return ret;

    }

    inline bigint&operator*=(const bigint&a)

    {

        bignum_t t;

        mul(t,num,a.num);

        memcpy(num,t,sizeof(bignum_t));

        sgn*=a.sgn;

        return*this;

    }

    inline bigint&operator*=(const ll a)

    {

        mul(num,ABS(a));

        sgn*=SGN(a);

        return*this;

    }

    inline bigint operator*(const bigint&a)

    {

        bigint ret;

        mul(ret.num,num,a.num);

        ret.sgn=sgn*a.sgn ;

        return ret;

    }

    inline bigint operator*(const ll a)

    {

        bigint ret;

        memcpy(ret.num,num,sizeof(bignum_t));

        mul(ret.num,ABS(a));

        ret.sgn=sgn*SGN(a);

        return ret;

    }

    inline bigint&operator/=(const bigint&a)

    {

        bignum_t t;

        div(t,num,a.num);

        memcpy (num,t,sizeof(bignum_t));

        sgn=(num[]==&&!num[])?:sgn*a.sgn ;

        return*this;

    }

    inline bigint&operator/=(const ll a)

    {

        ll t;

        div(num,ABS(a),t);

        sgn=(num[]==&&!num [])?:sgn*SGN(a);

        return*this;

    }

    inline bigint operator/(const bigint&a)

    {

        bigint ret;

        bignum_t t;

        memcpy(t,num,sizeof(bignum_t));

        div(ret.num,t,a.num);

        ret.sgn=(ret.num[]==&&!ret.num[])?:sgn*a.sgn ;

        return ret;

    }

    inline bigint operator/(const ll a)

    {

        bigint ret;

        ll t;

        memcpy(ret.num,num,sizeof(bignum_t));

        div(ret.num,ABS(a),t);

        ret.sgn=(ret.num[]==&&!ret.num[])?:sgn*SGN(a);

        return ret;

    }

    inline bigint&operator%=(const bigint&a)

    {

        bignum_t t;

        div(t,num,a.num);

        if(num[]==&&!num[])sgn=;

        return*this;

    }

    inline ll operator%=(const ll a)

    {

        ll t;

        div(num,ABS(a),t);

        memset(num,,sizeof(bignum_t));

        num[]=;

        add(num,t);

        return t;

    }

    inline bigint operator%(const bigint&a)

    {

        bigint ret;

        bignum_t t;

        memcpy(ret.num,num,sizeof(bignum_t));

        div(t,ret.num,a.num);

        ret.sgn=(ret.num[]==&&!ret.num [])?:sgn;

        return ret;

    }

    inline ll operator%(const ll a)

    {

        bigint ret;

        ll t;

        memcpy(ret.num,num,sizeof(bignum_t));

        div(ret.num,ABS(a),t);

        memset(ret.num,,sizeof(bignum_t));

        ret.num[]=;

        add(ret.num,t);

        return t;

    }

    inline ll operator>(const bigint&a)

    {

        return sgn>?(a.sgn>?comp(num,a.num)>:):(sgn<?(a.sgn<?comp(num,a.num)<:):a.sgn<);

    }

    inline ll operator>(const ll a)

    {

        return sgn>?(a>?comp(num,a)>:):(sgn<?(a<?comp(num,-a)<:):a<);

    }

    inline ll operator>=(const bigint&a)

    {

        return sgn>?(a.sgn>?comp(num,a.num)>=:):(sgn<?(a.sgn<?comp(num,a.num)<=:):a.sgn<=);

    }

    inline ll operator>=(const ll a)

    {

        return sgn>?(a>?comp(num,a)>=:):(sgn<?(a<?comp(num,-a)<=:):a<=);

    }

    inline ll operator<(const bigint&a)

    {

        return sgn<?(a.sgn<?comp(num,a.num)>:):(sgn>?(a.sgn>?comp(num,a.num)<:):a.sgn>);

    }

    inline ll operator<(const ll a)

    {

        return sgn<?(a<?comp(num,-a)>:):(sgn>?(a>?comp(num,a)<:):a>);

    }

    inline ll operator<=(const bigint&a)

    {

        return sgn<?(a.sgn<?comp(num,a.num)>=:):(sgn>?(a.sgn>?comp(num,a.num)<=:):a.sgn>=);

    }

    inline ll operator<=(const ll a)

    {

        return sgn<?(a<?comp(num,-a)>=:):(sgn>?(a>?comp(num,a)<=:):a>=);

    }

    inline ll operator==(const bigint&a)

    {

        return(sgn==a.sgn)?!comp(num,a.num):;

    }

    inline ll operator==(const ll a)

    {

        return(sgn*a>=)?!comp(num,ABS(a)):;

    }

    inline ll operator!=(const bigint&a)

    {

        return(sgn==a.sgn)?comp(num,a.num): ;

    }

    inline ll operator!=(const ll a)

    {

        return(sgn*a>=)?comp(num,ABS(a)): ;

    }

    inline ll operator[](const ll a)

    {

        return digit(num,a);

    }

    friend inline istream&operator>>(istream&is,bigint&a)

    {

        read(a.num,a.sgn,is);

        return is;

    }

    friend inline ostream&operator<<(ostream&os,const bigint&a)

    {

        if(a.sgn<) os<<'-';

        write(a.num,os);

        return os;

    }

    friend inline bigint sqrt(const bigint&a)

    {

        bigint ret;

        bignum_t t;

        memcpy(t,a.num,sizeof(bignum_t));

        sqrt(ret.num,t);

        ret.sgn=ret.num[]!=||ret.num[];

        return ret;

    }

    friend inline bigint sqrt(const bigint&a,bigint&b)

    {

        bigint ret;

        memcpy(b.num,a.num,sizeof(bignum_t));

        sqrt(ret.num,b.num);

        ret.sgn=ret.num[]!=||ret.num[];

        b.sgn=b.num[]!=||ret.num[];

        return ret;

    }

    inline ll length()

    {

        return :: length(num);

    }

    inline ll zeronum()

    {

        return :: zeronum(num);

    }

};

int main()

{

    int n,i;

    bigint x,ans;

    while(~scanf("%d",&n))

    {

        ans=;

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

        {

            cin>>x;

            ans=ans*x;

        }

        cout<<ans<<"\n";

    }

    return ;

}