压位高精乘[模版](update)

NuoCarter · 2020-06-23 18:57:32 · 个人记录

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int base=pow(10,9);
char str1[15005];
char str2[15005];
int lenstr1;
int lenstr2;
ll di1[15005];
ll di2[15005];
ll ans[30005];
int tot1;
int tot2;
int add1[15005];
int add2[15005];
int ans_add[20005];
inline void init(char* s,ll tep[],int len,int& tot){
    tot=0;
    int t=0;
    for(int i=len;i>8;i-=9){
        ++tot;
        for(int j=8;j>=0;--j){
            tep[tot]=tep[tot]*10+(s[i-j]-'0');
        }
    }

    int o=len%9;
    if(o>0){++tot;}
    for(int i=1;i<=o;++i){tep[tot]=tep[tot]*10+(s[i]-'0');}
    return;
}
inline int mul(ll a1[],ll a2[],ll a3[]){
    if(tot1==0||tot2==0){return 0;}
    int loc1;
    for(int i=1;i<=tot1;++i){
        loc1=i;
        for(int j=1;j<=tot2;++j){
            a3[loc1]+=a1[i]*a2[j];
            if(a3[loc1]>=1e9){
                a3[loc1+1]+=a3[loc1]/base;
                a3[loc1]%=base;
            }
            loc1++;
        }
    }
    if(a3[loc1]!=0){return loc1;}
    else{return loc1-1;}
}
int main(){
    scanf("%s",str1+1);
    lenstr1=strlen(str1+1);
    init(str1,di1,lenstr1,tot1);
    scanf("%s",str2+1);
    lenstr2=strlen(str2+1);
    init(str2,di2,lenstr2,tot2);
    int many=mul(di1,di2,ans);
    while(ans[many]==0&&many>1){
        many--;
    }
    cout<<ans[many];
    for(int i=many-1;i>=1;--i){printf("%0*lld",9,ans[i]);}
    return 0;
}