/ Vijos / 题库 / 高精度乘法 /

题解

334 条题解

  • 9
    @ 2017-08-16 21:13:26 
    #py大法好
a = int(input())
b = int(input())
print(a*b)
  • 7
    @ 2017-10-04 17:53:44 
    #include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

struct bigint
{
    vector<int> num;
    int operator == (bigint b)
    {
        if (num.size()!=b.num.size())
            return 0;
        else
        {
            for (unsigned long long i=0,size=num.size();i<size;i++)
                if (num[i]!=b.num[i])
                    return 0;
            return 1;
        }
    }
    int operator != (bigint b)
    {
        return ((!(*this==b))?1:0);
    }
    int operator < (bigint b)
    {
        if (num.size()<b.num.size())
            return 1;
        else if (num.size()>b.num.size())
            return 0;
        else
        {
            for (unsigned long long i=0,size=num.size();i<size;i++)
            {
                if (num[size-1-i]<b.num[size-1-i])
                    return 1;
                else if (num[size-1-i]>b.num[size-1-i])
                    return 0;
            }
            return 0;
        }
    }
    int operator > (bigint b)
    {
        if (num.size()<b.num.size())
            return 0;
        else if (num.size()>b.num.size())
            return 1;
        else
        {
            for (unsigned long long i=0,size=num.size();i<size;i++)
            {
                if (num[size-1-i]<b.num[size-1-i])
                    return 0;
                else if (num[size-1-i]>b.num[size-1-i])
                    return 1;
            }
            return 0;
        }
    }
    int operator <= (bigint b)
    {
        return ((!(*this>b))?1:0);
    }
    int operator >= (bigint b)
    {
        return ((!(*this<b))?1:0);
    }
    bigint mov(long long x)
    {
        bigint ans;
        ans.num.clear();
        if (x+num.size()>0)
        {
            ans.num.resize(num.size()+x,0);
            for (long long i=0,size=num.size();i<size;i++)
                if (i+x>=0)
                    ans.num[i+x]=num[i];
        }
        else
            ans=0;
        return ans;
    }
    bigint operator = (long long b)
    {
        char s[20+1];
        sprintf(s,"%lld",b);
        num.clear();
        num.resize(strlen(s));
        for (unsigned long long i=0,size=num.size();i<size;i++)
            num[i]=(s[size-1-i]-'0');
        return (*this);
    }
    bigint operator = (string b)
    {
        num.clear();
        num.resize(b.size());
        for (unsigned long long i=0,size=num.size();i<size;i++)
            num[i]=(b[size-1-i]-'0');
        return (*this);
    }
    bigint operator + (bigint b)
    {
        bigint ans;
        ans.num.clear();
        ans.num.resize(max(num.size(),b.num.size()));
        for (unsigned long long i=0,size=ans.num.size();i<size;i++)
            ans.num[i]=((i<num.size())?num[i]:0)+((i<b.num.size())?b.num[i]:0);
        for (unsigned long long i=0,size=ans.num.size();i<size;i++)
        {
            if (ans.num[i]>=10&&i==size-1)
                ans.num.resize(++size);
            ans.num[i+1]+=(ans.num[i]/10);
            ans.num[i]%=10;
        }
        return ans;
    }
    bigint operator += (bigint b)
    {
        return (*this=(*this+b));
    }
    bigint operator - (bigint b)
    {
        bigint ans;
        if ((*this)==b)
        {
            ans=0;
            return ans;
        }
        ans.num.clear();
        ans.num.resize(max(num.size(),b.num.size()));
        for (unsigned long long i=0,size=ans.num.size();i<size;i++)
            ans.num[i]=((i<num.size())?num[i]:0)-((i<b.num.size())?b.num[i]:0);
        for (unsigned long long i=0,size=ans.num.size();i<size;i++)
            while (ans.num[i]<0)
                ans.num[i]+=10,ans.num[i+1]--;
        while (ans.num[ans.num.size()-1]==0)
            ans.num.resize(ans.num.size()-1);
        return ans;
    }
    bigint operator -= (bigint b)
    {
        return (*this=(*this-b));
    }
    bigint operator * (bigint b)
    {
        bigint ans,num_0;
        num_0=0;
        ans.num.clear();
        if (*this!=num_0&&b!=num_0)
        {
            ans.num.resize(num.size()+b.num.size()-1);
            for (unsigned long long i=0,size_1=num.size();i<size_1;i++)
                for (unsigned long long j=0,size_2=b.num.size();j<size_2;j++)
                    ans.num[i+j]+=(num[i]*b.num[j]);
            for (unsigned long long i=0,size=ans.num.size();i<size;i++)
            {
                if (ans.num[i]>=10&&i==size-1)
                    ans.num.resize(++size);
                ans.num[i+1]+=(ans.num[i]/10);
                ans.num[i]%=10;
            }
        }
        else
            ans=0;
        return ans;
    }
    bigint operator *= (bigint b)
    {
        return (*this=(*this*b));
    }
    bigint operator / (bigint b)
    {
        bigint ans,num_0;
        num_0=0;
        if (*this<b)
            return num_0;
        if (*this!=num_0&&*this>num_0)
        {
            bigint x,y;
            x=*this,y=b.mov(num.size()-b.num.size());
            ans.num.resize(num.size()-b.num.size()+1,0);
            for (long long i=ans.num.size()-1;i>=0;i--,y=y.mov(-1))
                while (x>=y)
                    x-=y,ans.num[i]++;
            for (unsigned long long i=0,size=ans.num.size();i<size;i++)
            {
                if (ans.num[i]>=10&&i==size-1)
                    ans.num.resize(++size);
                ans.num[i+1]+=(ans.num[i]/10);
                ans.num[i]%=10;
            }
            while (ans.num.size()>1&&ans.num[ans.num.size()-1]==0)
                ans.num.resize(ans.num.size()-1);
        }
        else
            ans=0;
        return ans;
    }
    bigint operator /= (bigint b)
    {
        return (*this=(*this/b));
    }
    void print()
    {
        for (unsigned long long i=0,size=num.size();i<size;i++)
            printf("%d",num[size-1-i]);
    }
};

char s[10000+1];
#define s(x) s[x-1]
bigint a,b,c;
string s_a,s_b;
#define s_a(x) s_a[x-1]
#define s_b(x) s_b[x-1]

int main()
{
    while (~scanf("%s",s))
    {
        s_a=s;
        getchar();
        scanf("%s",s);
        s_b=s;
        getchar();
        a=s_a,b=s_b;
        c=a*b;
        c.print();
        printf("\n");
    }
}
  • 2
    @ 2017-07-22 11:30:45

    #include <iostream>
    #include <iomanip>
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <algorithm>
    #include <cctype>
    #include <vector>
    #include <queue>
    #include <set>
    #include <bitset>
    #include <cassert>
    #include <map>
    #include <string>
    #include <sstream>
    #include <ctime>
    using namespace std;
    int a[20010],b[20010],c[20010];
    char s1[20010],s2[20010],s3[20010];
    int main()
    {
    int la,lb,l;
    scanf("%s%s",s1,s2);
    la=strlen(s1);
    lb=strlen(s2);
    for(int i=1;i<=la;i++)
    {
    a[i]=s1[la-i]-'0';
    }
    for(int i=1;i<=lb;i++)
    {
    b[i]=s2[lb-i]-'0';
    }
    for(int i=1;i<=la;i++)
    {
    for(int j=1;j<=lb;j++)
    {
    c[i+j-1]=c[i+j-1]+a[i]*b[j];
    c[i+j]=c[i+j]+c[i+j-1]/10;
    c[i+j-1]=c[i+j-1]%10;
    }
    }
    l=la+lb;
    while(c[l]==0&&l>1)
    {
    l--;
    }
    for(int i=l;i>=1;i--)
    {
    printf("%d",c[i]);
    }
    return 0;
    }

  • 2
    @ 2016-11-05 11:04:49

    蒟蒻写的非常简单的代码，并没有用FFT或者压位什么的
    但是居然AC了......
    供参考
    c++
    #include <cstdio>
    #include <cstring>
    using namespace std;
    int a[10001],b[10001],c[20001];
    char s1[10001],s2[10001];
    int main() {
    gets(s1);gets(s2);
    int i,j,l1=strlen(s1),l2=strlen(s2),x=0;
    for (i=1;i<=l1;i++) a[i]=s1[l1-i]-48;
    for (i=1;i<=l2;i++) b[i]=s2[l2-i]-48;
    for (i=1;i<=l1;i++)
    for (j=1;j<=l2;j++)
    c[i+j]+=a[i]*b[j];
    for (i=1;i<=l1+l2;i++) { //统一整理进位
    c[i+1]+=c[i]/10;
    c[i]%=10;
    }
    int max=l1+l2+1;
    while (c[max]==0) max--; //去除数字前的零
    for (i=max;i>=2;i--) printf("%d",c[i]);
    printf("\n");
    return 0;
    }

  • 1
    @ 2022-05-22 19:42:37

    python的巅峰时刻:

    n=int(input())
m=int(input())
print(x*y)
  • 1
    @ 2020-07-12 14:05:39 
    x=int(input())
y=int(input())
print(x*y)

    真香！！

  • 1
    @ 2018-11-09 21:48:53

    告诉你什么叫做流！弊！
    Python3三行代码解决：

    x=int(input()) #input()用于读入一行字符，int()用于把字串转为数字
y=int(input());#在python中分号可以省略，也可以加上
print(x*y)     #输出a*b，python中有乘方运算符（^）

    哇哈哈哈哈哈哈哈哈哈哈哈哈~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    //笑出猪叫

  • 1
    @ 2018-07-04 00:00:44

    #include <iostream>
    #include <cstring>
    using namespace std;
    int a[10601],b[10601],c[20601];
    int main(int argc, char** argv)
    {
    int la,lb,x=0,o;
    string A,B;
    cin>>A>>B;
    la=A.length();
    lb=B.length();
    for(int i=1;i<=la;i++)
    {
    a[i]=A[la-i]-'0';
    }
    for(int j=1;j<=lb;j++)
    {
    b[j]=B[lb-j]-'0';
    }
    for(int k=1;k<=la;k++)
    {
    for(int l=1;l<=lb;l++)
    {
    c[k+l-1]=a[k]*b[l]+c[k+l-1]+x;
    x=c[k+l-1]/10;
    c[k+l-1]=c[k+l-1]%10;
    }
    c[k+lb]=x;
    x=0;
    }
    o=la+lb;
    while(c[o]==0&&o!=0)
    {
    o--;
    }
    for(int oo=o;oo>=1;oo--)
    {
    cout<<c[oo];
    }
    return 0;
    }

  • 1
    @ 2018-03-18 10:01:31

    这题用Java无敌

    import java.math.BigInteger;
    import java.util.Scanner;

    public class Main
    {
    public static void main(String[] args)
    {
    Scanner scan=new Scanner(System.in);
    BigInteger a=scan.nextBigInteger();
    BigInteger b=scan.nextBigInteger();
    BigInteger c=a.multiply(b);
    System.out.println(c);
    }

    }

  • 1
    @ 2017-12-11 22:02:11

    #include<cstdio>
    #include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    string tp;

    struct u{
    int A[10000],len;

    //构造函数 指的是 一开始变量生成的时候做的初始化操作
    u(){
    memset(A,0,sizeof(A));
    len=1;
    }

    u (string a){
    memset(A,0,sizeof(A));
    this->len=0;
    for(int i=a.length()-1;i>=0;i--){
    this->A[this->len]=a[i]-'0';
    this->len++;
    }
    }
    void pt(){
    for(int i=this->len-1;i>=0;i--){
    printf("%d",A[i]);
    }
    //printf("\n%d",len);
    }

    u operator * (u s)//重载运算符 *
    {

    u ans;
    int maxlen=this->len+s.len+1;
    for(int i=0;i<s.len;i++){
    for(int j=0;j<this->len;j++){
    ans.A[i+j]+=this->A[j]*s.A[i];
    ans.A[i+j+1]+=ans.A[i+j]/10;
    ans.A[i+j]%=10;
    }
    }
    while(ans.A[maxlen]==0 && maxlen>0) maxlen--;
    ans.len=maxlen+1;
    return ans;
    }

    };

    int main(){
    cin>>tp;
    u a(tp);
    cin>>tp;
    u b(tp);
    u c=a*b;
    c.pt();
    return 0;
    }

  • 1
    @ 2017-10-18 17:40:38

    QAQ

    #include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cstdlib>
#include<cmath>
#define maxn 100005
using namespace std;
char s1[maxn],s2[maxn];
int c[maxn],a1[maxn],a2[maxn];
void mul(int a[],int b[]){
    for(int i=1;i<=a[0];i++){
        for(int j=i;j<=b[0]+i-1;j++){
            c[j]+=a[i]*b[j-i+1];
            if(c[j]>=10){
                c[j+1]+=c[j]/10;
                c[j]=c[j]%10;
            }
        }
    }c[0]=a[0]+b[0];
    while(c[c[0]]==0&&c[0]>0){c[0]--; }
    while(c[c[0]+1]){
        c[0]++;
        c[c[0]+1]+=c[c[0]]/10;
        c[c[0]]%=10;
    }
} 
int main(){
    scanf("%s%s",s1+1,s2+1);
    int len1=strlen(s1+1),len2=strlen(s2+1);
    for(int i=1;i<=len1;i++){
        a1[i]=s1[len1-i+1]-'0';
    }
    for(int i=1;i<=len2;i++){
        a2[i]=s2[len2-i+1]-'0';
    }a1[0]=len1,a2[0]=len2;
    mul(a1,a2);
    for(int i=c[0];i>=1;i--){
        printf("%d",c[i]);
    }
}
  • 1
    @ 2017-08-18 16:18:30

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <vector>
    #include <algorithm>
    #include <set>
    #include <map>
    #include <bitset>
    #include <cmath>
    #include <queue>
    #include <stack>
    using namespace std;

    int main()
    {
    char a[10000] , b[10000];
    int n[10000]={} , m[10000]={} , result[10000] = {};
    int la , lb , i , j , w = 0;
    int k = w;
    cin >> a >> b;
    la = strlen(a);
    lb = strlen(b);
    for(i = 0;i < la;i++) n[i] = a[la-i-1] - '0';
    for(i = 0;i < lb;i++) m[i] = b[lb-i-1] - '0';
    for(i = 0;i < la;i++)
    for(j = 0;j < lb;j++)
    {
    result[i + j] += n[i] * m[j];
    if(result[i + j] != 0) w = i + j;
    }
    for(i = 0;i <= w + 5;i++)
    {
    result[i + 1] += result[i] / 10;
    result[i] %= 10;
    if(result[i] != 0) k = i;
    }
    for(i = k;i >= 0;i--) cout << result[i];
    return 0;
    }

  • 1
    @ 2017-08-16 18:39:53

    好短的主函数
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    char cd[100000];
    void maint(char ak[10001],char bk[10001])
    {
    int a[100000],b[100000],c[100001],d,e,f,z=0;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    d=strlen(ak);
    e=strlen(bk);
    for(int i=0;i<=d-1;++i)
    {
    a[d-i]=ak[i]-48;
    }
    for(int j=0;j<=e-1;++j)
    {
    b[e-j]=bk[j]-48;
    }
    for(int q=1;q<=d;++q)
    {
    z=0;
    for(int v=1;v<=e;++v)
    {
    c[q+v-1]=a[q]*b[v]+z+c[q+v-1];
    z=c[q+v-1]/10;
    c[q+v-1]=c[q+v-1]%10;
    }
    c[q+e]=z;
    }
    f=d+e;
    while((c[f]==0)&&(f>1))
    {
    f--;
    }
    for(int u=1;u<=f;++u)
    {
    cd[u]=0;
    }
    for(int u=f;u>=1;u--)
    {
    cd[f-u]=c[u]+48;
    }
    cout<<cd;
    }
    int main()
    {
    char a[10001],b[10001];
    cin>>a>>b;
    maint(a,b);
    }

  • 1
    @ 2017-07-29 22:13:54 
    #include <cstdio>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
#define MAX 1
// D[i] : 0....99999
int pow_int(int a,int n)
{
    int count=1,x=a;
    while(n>0)
    {
        if(n&1)
            count*=x;
        x=x*x;
        n=n>>1;
    }
    return count;
}
struct BigInt
{
    int D[100000];       
    int max;
    int n;
    BigInt(int x)
    {
        fill(D,D+100,0);
        int i;
        max=pow_int(10,MAX);
        for(i=0;x>0;i++)
        {
            D[i]=x%max;
            x=x/max;
        }
        n=i;
    }
    BigInt(void)    
    {
        fill(D,D+100,0);
        n=0;
        max=pow_int(10,MAX);
    }
    void print(void)
    {
        cout<<D[n-1];   
        for(int i=n-2;i>=0;i--)
        {
            cout<<D[i]; 
        }
        cout<<endl;
    }
};
BigInt &mul(BigInt &a,BigInt &b);
int main()
{
    string s1,s2;
    cin>>s1>>s2;
    BigInt a,b;
    for(int i=s1.size()-1,j=0;i>=0;i--,j++)
        a.D[j]=s1[i]-'0';
    a.n=s1.size();
    for(int i=s2.size()-1,j=0;i>=0;i--,j++)
        b.D[j]=s2[i]-'0';
    b.n=s2.size();
    BigInt result=mul(a,b);
    result.print();
    return 0;
}

BigInt &mul(BigInt &a,BigInt &b)
{
    BigInt *result=new BigInt(0);
    for(int i=0;i<a.n;i++)
    {
        for(int j=0;j<b.n;j++)
        {
            result->D[i+j]+=a.D[i]*b.D[j];
            if(result->D[i+j]>=result->max)
                result->D[i+j+1]+=result->D[i+j]/result->max;
                result->D[i+j]=result->D[i+j]%result->max;
        }
    }
    result->n=a.n+b.n-1;
    
    while(result->D[result->n]==0&&result->n>1)
    {
        result->n--;
    }
    if(result->D[result->n])
        result->n++;
    return *result;
}
  • 0
    @ 2022-05-10 12:55:52

    a = int(input())

    b = int(input())

    print(a*b)

  • 0
    @ 2022-05-10 12:54:57

    d = int(input())
    f = int(input())
    print(d*f)
    //ha,ha,用c++的手都要残了

  • 0
    @ 2021-09-27 17:14:33

    py 无敌！自带高精度！

    a = int(input())
b = int(input())
print(a*b)
  • 0
    @ 2020-12-31 00:51:52 
    #include<bits/stdc++.h>
#define ll long long int
using namespace std;
struct bigint{
    int a[7000],n,N=1000,t=3;
    bigint (){
        memset(a,0,sizeof(a));
    }
    bigint(char* s,int _n){
        memset(a,0,sizeof(a));
        char* _end=s+_n,*beg;
        int p=0;
        while(_end-t>s){
            beg=_end-t;
            for(int i=0;i<t;i++){
                a[p]*=10;
                a[p]+=beg[i]-'0';
            }
            ++p;
            _end=beg;
        }
        if(_end>s){
            for(int i=0;i<_end-s;i++){
                a[p]*=10;
                a[p]+=s[i]-'0';
            }
            ++p;
        }
        n=p;
    }
    int& operator [](int i){
        return a[i];
    }
    bigint operator * (bigint& b){
        int i,j,m=b.n;
        bigint r;
        int sr=n+m-1;
        for(i=0;i<n;++i)
            for(j=0;j<m;++j)
                r[i+j]+=a[i]*b[j];
        for(i=0;i<sr;++i){
            r[i+1]+=r[i]/N;
            r[i]%=N;
        }
        if(r[sr])sr++;
        r.n=sr;
        return r;
    }
    void show(){
        int i=n-2;
        printf("%d",a[n-1]);
        while(i>=0)
            printf("%03d",a[i--]);
    }
};

char s[10001];
int main() {
    //freopen("in.txt","r",stdin);
   scanf("%s",s);
   bigint a(s,strlen(s));
   scanf("%s",s);
   bigint b(s,strlen(s));
   (a*b).show();
}

    后两个wa了的，可能是中间爆int了，压四位先乘了再进位会爆int...要不用longlong 要不就压三位

  • 0
    @ 2020-07-12 17:19:02

    #include<iostream>
    #include<string>
    using namespace std;
    const int N = 10001;
    void h_multiply_2(int a[], int b[], int c[])
    {
    int la = a[0];
    int lb = b[0];
    for(int i=1;i<=la;i++)
    {
    for(int j=1;j<=lb;j++)
    {
    c[i+j-1] += a[i] * b[j];
    }
    }
    for(int i=1;i<=la+lb;i++)
    {
    c[i+1] += c[i] / 10;
    c[i] %= 10;
    }
    c[0] = la+lb;
    }
    int convert(string s,int n[])
    {
    int length = s.length();
    for(int i=1;i<=length;i++)
    {
    n[i] = s[length-i] - '0';
    }
    n[0] = length;
    return length;
    }
    void output(int n[])//n是算好了的高精度数
    {
    int length = n[0];
    if(length==0)
    {
    cout << 0 << endl;
    return;
    }
    for(int i=length;i>=1;i--)
    {
    cout << n[i];
    }
    cout << endl;
    }
    int trim(int n[])
    {
    int length = 0;
    for(int i=n[0];i>0;i--)
    {
    if(n[i]!=0)
    {
    length = i;
    break;
    }
    }
    n[0] = length;
    return length;
    }
    int a[N+1];
    int b[N+1];
    int c2[2*N+1];
    int main()
    {
    string s1, s2;
    cin >> s1 >> s2;
    convert(s1, a);
    convert(s2, b);
    h_multiply_2(a,b,c2);
    trim(c2);
    output(c2);
    return 0；
    }

  • 0
    @ 2018-09-12 16:50:14

    其实，除了Python,Haskell也可以一行

    main = do { a<-readLn; b<-readLn; print (a*b) }

高精度乘法

信息

ID
1040
难度
7
分类
高精度 点击显示
标签
(无)
递交数
16426
已通过
3139
通过率
19%
被复制
19
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1