首页 > 试题广场 > 大整数相乘
[编程题]大整数相乘
  • 热度指数:36434 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
有两个用字符串表示的非常大的大整数,算出他们的乘积,也是用字符串表示。不能用系统自带的大整数类型。

输入描述:
空格分隔的两个字符串,代表输入的两个大整数


输出描述:
输入的乘积,用字符串表示
示例1

输入

72106547548473106236 982161082972751393

输出

70820244829634538040848656466105986748
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner in=new Scanner(System.in);
		String num1=in.nextBigDecimal().toString();
		String num2=in.nextBigDecimal().toString();
		int[] ret=new int[num1.length()+num2.length()];
		for(int i=num1.length()-1;i>=0;i--){
			int x=num1.charAt(i)-'0';
			for(int j=num2.length()-1;j>=0;j--){
				int y=num2.charAt(j)-'0';
				ret[i+j]+=(ret[i+j+1]+x*y)/10;
				ret[i+j+1]=(ret[i+j+1]+x*y)%10;
				
			}
		}
		String s="";
		for(int i=0;i<ret.length;i++){
			if(i==0&&ret[i]==0) continue;
			s+=ret[i];
		}
		System.out.println(s);
	}
}


发表于 2017-08-07 01:55:28 回复(19)
//AC代码:
#include<stdio.h>
#include<string>
#include<iostream>
using namespace std;
const int L=11000;  
string mul(string,string);
int main(){
	string x,y;
	while(cin>>x>>y)
		cout<<mul(x,y)<<endl;
}
string mul(string a,string b) {  
    string s;  
    int na[L],nb[L],nc[L],La=a.size(),Lb=b.size(),i,j;
    fill(na,na+L,0);fill(nb,nb+L,0);fill(nc,nc+L,0);
    for(i=La-1;i>=0;i--) na[La-i]=a[i]-'0';
    for(i=Lb-1;i>=0;i--) nb[Lb-i]=b[i]-'0';  
    for(i=1;i<=La;i++)  
        for(j=1;j<=Lb;j++)  
        nc[i+j-1]+=na[i]*nb[j];
    for(i=1;i<=La+Lb;i++)  
        nc[i+1]+=nc[i]/10,nc[i]%=10;
    if(nc[La+Lb]) s+=nc[La+Lb]+'0';
    for(i=La+Lb-1;i>=1;i--)  
        s+=nc[i]+'0';
    return s;  
}  

发表于 2017-08-06 10:43:40 回复(13)

import java.util.Scanner;

/**

  • Created by linjian on 17/8/5.
    */
    public class Main {
    public static void main(String[] args) {
     Scanner scanner = new Scanner(System.in);
     String num1 = scanner.next();
     String num2 = scanner.next();
     System.out.println(multiply(num1,num2));
    
    }
    public static String multiply(String num1, String num2) {
     num1 = new StringBuilder(num1).reverse().toString();
     num2 = new StringBuilder(num2).reverse().toString();
     // even 99 * 99 is < 10000, so maximaly 4 digits
     int[] d = new int[num1.length() + num2.length()];
     for (int i = 0; i < num1.length(); i++) {
         int a = num1.charAt(i) - '0';
         for (int j = 0; j < num2.length(); j++) {
             int b = num2.charAt(j) - '0';
             d[i + j] += a * b;
         }
     }
     StringBuilder sb = new StringBuilder();
     for (int i = 0; i < d.length; i++) {
         int digit = d[i] % 10;
         int carry = d[i] / 10;
         sb.insert(0, digit);
         if (i < d.length - 1)
             d[i + 1] += carry;
     }
     //trim starting zeros
     while (sb.length() > 0 && sb.charAt(0) == '0') {
         sb.deleteCharAt(0);
     }
     return sb.length() == 0 ? "0" : sb.toString();
    
    }
    }
发表于 2017-08-05 19:38:16 回复(10)
a,b = map(int,raw_input().split()) 
print str(a*b)
这竟然也过了,有点慌。。。
发表于 2017-08-07 11:04:11 回复(15)
import sys
s=sys.stdin.readline().strip().split()
def karatsuba_mul(num1, num2):
    #karatsuba算法
    if len(str(num1))==1 or len(str(num2))==1:
        return num1*num2
    n=max(len(str(num1)),len(str(num2)))
    half=n//2
   
    a=num1//10**half
    b=num1%10**half
    c=num2//10**half
    d=num2%10**half
    ac=karatsuba_mul(a,c) #计算a*c
    bd=karatsuba_mul(b,d) #计算b*d
    abcd=karatsuba_mul(a+b,c+d) #计算(a+b)*(c+d)
    adbc=abcd-ac-bd
    return ac*10**(2*half)+adbc*10**half+bd
print(str(karatsuba_mul(int(s[0]), int(s[1]))))


编辑于 2019-03-18 19:49:42 回复(2)

python

a, b = map(int, input().split())
print(a * b)
发表于 2019-02-24 15:29:43 回复(3)
//写的不太好
#include <iostream>
#include <string>
using namespace std;
string addOfString(string s1, string s2)
{
    string res = "";
    if (s1.size()<s2.size())
        s1 = string(s2.size() - s1.size(), '0') + s1;
    else
        s2 = string(s1.size() - s2.size(), '0') + s2;
    int carry = 0;
    for (int i = s1.size() - 1; i >= 0; --i)
    {
        char temp = (s1[i] - '0' + s2[i] - '0' + carry) % 10 + '0';
        res = temp + res;
        carry = (s1[i] - '0' + s2[i] - '0' + carry) / 10;
    }
    if (carry)    res = '1' + res;
    return res;
}

string multiplyOfString(string s1, string s2)
{
    string res = "";
    string shorter = s1.size() < s2.size() ? s1 : s2;
    string longer = s1.size() < s2.size() ? s2 : s1;
    for (int i = shorter.size()-1; i >= 0; --i)
    {
        string temp = "";
        for (int j = 0; j < shorter[i] - '0'; ++j)
            temp = addOfString(temp, longer);
        res = addOfString(temp + string(shorter.size() - i - 1, '0'), res);
    }
    return res;
}
int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    cout << multiplyOfString(s1, s2) << endl;
}
//看大家的评论发现可以直接乘不用加法,因此又写了一个方法二:
#include <iostream>
#include <string>
using namespace std;
string multiplyOfString(string s1, string s2)
{
    string res(s1.size()+s2.size(),'0');
    string shorter = s1.size() < s2.size() ? s1 : s2;
    string longer = s1.size() < s2.size() ? s2 : s1;
    for (int i = shorter.size() - 1; i >= 0; --i)
    {
        int carry = 0;//进位
        for (int j = longer.size() - 1; j >= 0; --j)
        {
            int temp = (longer[j] - '0')*(shorter[i] - '0')+ carry + res[i+j+1] - '0';
            res[i + j + 1] = temp % 10 + '0';
            carry = temp / 10;
            if (carry&&j == 0)//如果短串已经到最左边(j==0)并且carry是不为0的,那么res要修改;
                res[i] += carry;
        }
    }
    //去掉前排的0
    int i = 0;
    while (res[i] == '0')//此处不要写i++;
        res.erase(0, 1);
    return res;
}

int main()
{
    string s1, s2;
    cin >> s1 >> s2;
    cout << multiplyOfString(s1, s2) << endl;
} 

编辑于 2019-03-25 12:59:13 回复(6)
import java.util.Scanner;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            char[] s1 = scanner.next().toCharArray();
            char[] s2 = scanner.next().toCharArray();

            int len = s1.length + s2.length;
            char[] res = new char[len];
            for (int i = 0; i < len; i++) res[i] = '0';

            for (int i = s1.length - 1; i >= 0; i--) {
                int cur = s1.length - i - 1, multiplier = s1[i] - '0', carry = 0;

                for (int j = s2.length - 1; j >= 0; j--) {
                    int product = (res[cur] - '0') + multiplier * (s2[j] - '0') + carry;
                    res[cur++] = (char) (product % 10 + '0');
                    carry = product / 10;
                }

                if (carry != 0) res[cur] = (char) (carry + '0');
            }

            int i = len - 1;
            while (i >= 0 && res[i] == '0') i--; //忽略前导0
            if (i < 0) {
                System.out.println(0);
            }else {
                for (; i >= 0; i--) System.out.print(res[i]);
                System.out.println();
            }
        }
    }
}

发表于 2019-01-12 00:53:10 回复(0)

Python版:通过十进制的运算,并且注意到十进制中可能发生的连续进位问题(不然可能通过率很低),欢迎大家指正问题!

时间:40ms 内存:3568K


#创建指定大小的一维空数组
def kong(num):
    s=[]
    for i in range(num):
        s.append(0);
    return s

#十进制计算方法
def jinzhi(a,b):
    cz=a+b;
    if cz>= 10:
        return [cz-10,1]
    else:
        return [cz,0]

#十进制中有连续进位,设置递归进行运算
def jinzhi2(c,i,j):
    m=c[i+j]+1;
    if m!=10:
        c[i + j]=m;
    else:
        c[i+j]=0;
        jinzhi2(c,i,j-1);

#主程序
def bignum_multi(cc):
    dd = cc.split(' ');
    a = dd[0];
    b = dd[1];
    m = len(a);
    n = len(b);
    p = m + n;#两个数相乘的位数为m+n-1或者m+n
    c = kong(p);
    
    #主程序
    for i in range(n - 1, -1, -1):
        for j in range(m - 1, -1, -1):
            k = int(b[i]) * int(a[j]);
            k1 = k // 10;
            k2=k - k1 * 10;
            t = jinzhi(c[i+j+1],k2);
            c[i + j +1]=t[0];
            if t[1] == 1:
                jinzhi2(c, i, j);
            t = jinzhi(c[i + j], k1);
            c[i + j] = t[0];
            if t[1] == 1:
                jinzhi2(c, i, j-1);
                
    #数组转成字符串
    mm = "";
    if c[0] == 0:
        for i in range(1, p):
            mm = mm + str(int(c[i]));
    else:
        for i in range(p):
            mm = mm + str(int(c[i]));
    print(mm)

cc=input();
bignum_multi(cc);
发表于 2019-02-28 19:15:34 回复(0)
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main()
{
    string num1, num2;
    string s = "";
    cin >> num1 >> num2;
    int len1 = num1.size();
    int len2 = num2.size();
    vector<int> vTemp(len1 + len2 - 1);
    int n1, n2;
    for (int i = 0; i<len1; i++)
    {
        n1 = num1[i] - '0';
        for (int j = 0; j <len2; j++)
        {
            n2 = num2[j] - '0';
            vTemp[i + j] += n1*n2;
        }
    }
    int carry = 0;
    int tmp;
    for (int i = vTemp.size()-1; i >= 0; i--)
    {
        tmp = vTemp[i] + carry;
        vTemp[i] = tmp % 10;
        s = to_string(vTemp[i])+s;
        carry = tmp / 10;
    }
    if(carry > 0)
        s = to_string(carry)+s;
    cout << s << endl;
    return 0;
}

发表于 2018-08-05 16:31:52 回复(3)
#include <iostream>
#include <cstring>

int multi(const char* lhs, const char* rhs, char* result) {
	if (lhs == NULL || rhs == NULL || result == NULL)
		return 0;

	int llen = strlen(lhs), rlen = strlen(rhs);
	if (llen == 0 || rlen == 0)
		return 0;

	// 用rhs每一位去乘lhs,模拟手工算乘法的过程。
	int length = llen + rlen - 1;
	for (int j = rlen - 1; j >= 0; j--) {
		int carry = 0;		// 乘法进位
		for (int i = llen - 1; i >= 0; i--) {
			int temp = (rhs[j] - '0') * (lhs[i] - '0') + carry;
			// 根据位偏移将本位的结果加到result中去并处理加法进位。(result为倒序)
			int bit = llen - i - 1 + (rlen - j - 1);
			if ((result[bit] += temp % 10) >= '0' + 10) {
				result[bit + 1] += (result[bit] - '0') / 10;
				result[bit] = (result[bit] - '0') % 10 + '0';
			}
			// 保留进位。
			carry = temp / 10;
		}
		// 最高位有进位
		if (carry > 0) {
			result[llen + (rlen - j - 1)] += carry;
			length++;
		}
	}

	// 去掉多余的0
	while (result[length - 1] == '0')
		length--;

	return length;
}

int main() {
	char a[999];
	char b[999];
	scanf("%s%s", a, b);

	char r[999999];
	memset(r, '0', sizeof(r));
	int length = multi(a, b, r);

	while (--length >= 0) {
		std::cout << r[length];
	}

	system("pause");
	return 0;
}

发表于 2017-08-06 22:30:16 回复(0)
# coding=utf-8

def fun(l):
    num0,num1 = l[0],l[1]
    result = 0
    # 还原乘法的过程,按位相乘再乘以位数权重
    for i in range(len(num0)):
        for j in range(len(num1)):
            # 注意计算位数权重时,index越大位数越小
            result += int(num0[i])*int(num1[j])*pow(10,len(num0)-1-i+len(num1)-1-j) 
    return (str(result))

if __name__=='__main__':
    s = raw_input()
    l = s.split(' ')
    print(fun(l))
    

发表于 2019-01-15 16:03:15 回复(1)
模拟手算过程:

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    private static String add(String n1, String n2) {
        StringBuilder res = new StringBuilder();
        int p1 = n1.length() - 1;
        int p2 = n2.length() - 1;
        int carry = 0;
        while (carry > 0 || p1 >= 0 || p2 >= 0) {
            int value = carry + (p1 >= 0 ? n1.charAt(p1) - '0' : 0) + (p2 >= 0 ? n2.charAt(p2) - '0' : 0);
            res.append(value % 10);
            carry = value / 10;
            if (p1 >= 0) p1--;
            if (p2 >= 0) p2--;
        }
        return res.reverse().toString();
    }

    private static String singleMul(String n1, char n2) {
        StringBuilder res = new StringBuilder();
        int p = n1.length() - 1;
        int carry = 0;
        while (carry > 0 || p >= 0) {
            int value = carry + (n2 - '0') * (p >= 0 ? n1.charAt(p) - '0' : 0);
            res.append(value % 10);
            carry = value / 10;
            if (p >= 0) p--;
        }
        return res.reverse().toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String n1 = scanner.next();
        String n2 = scanner.next();
        if (n1.length() < n2.length()) {
            String tmp = n1;
            n1 = n2;
            n2 = tmp;
        }
        List<String> sums = new ArrayList<>();
        for (int i = n2.length() - 1; i >= 0; i--) {
            sums.add(singleMul(n1, n2.charAt(i)) + new String(new char[n2.length() - 1 - i]).replace('\0', '0'));
        }
        String res = "0";
        for (String s : sums) {
            res = add(res, s);
        }
        System.out.println(res);
    }
}

运行时间:74ms

占用内存:11272k


发表于 2019-03-13 00:33:42 回复(0)
N,M = input().strip().split()
print(eval(N) * eval(M))

一个用python答题者的心里过程:
为了显示我的能力,我表示我不用库函数都能写出来!
对着题思考十秒钟...
呵呵,这个库函数真好用

发表于 2018-01-25 16:48:58 回复(0)
直接模拟乘法的竖式计算过程,不过要注意计算加法的时候数字排列是阶梯状的,需要在数的后面补0。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strNum = br.readLine().trim().split(" ");
        System.out.println(multiply(strNum[0].toCharArray(), strNum[1].toCharArray()));
    }
    
    // 模拟乘法竖式
    private static String multiply(char[] num1, char[] num2) {
        if(num1.length < num2.length){
            char[] temp = num1;
            num1 = num2;
            num2 = temp;
        }
        Stack<String> stack = new Stack<>();
        for(int j = num2.length - 1; j >= 0; j--){
            StringBuilder sb = new StringBuilder();
            // 之后做竖式加法要补0
            for(int k = 0; k < num2.length - 1 - j; k++) sb.append(0);
            int carry = 0;
            for(int i = num1.length - 1; i >= 0; i--){
                int num = (num1[i] - '0')*(num2[j] - '0') + carry;
                carry = num / 10;
                sb.append(num % 10);
            }
            if(carry > 0) sb.append(carry);
            if(stack.isEmpty())
                stack.push(sb.reverse().toString());
            else{
                String temp = stack.pop();
                stack.push(add(temp, sb.reverse().toString()));
            }
        }
        return stack.pop();
    }
    
    private static String add(String num1, String num2) {
        if(num1.length() < num2.length()){
            String temp = num1;
            num1 = num2;
            num2 = temp;
        }
        int len1 = num1.length();
        int len2 = num2.length();
        int i = len1 - 1, j = len2 - 1;
        int carry = 0;
        StringBuilder sb = new StringBuilder();
        while(i >= 0 && j >= 0){
            int num = (num1.charAt(i) - '0') + (num2.charAt(j) - '0') + carry;
            carry = num / 10;
            sb.append(num % 10);
            i--;
            j--;
        }
        while(i >= 0){
            int num = (num1.charAt(i) - '0') + carry;
            carry = num / 10;
            sb.append(num % 10);
            i--;
        }
        if(carry > 0) sb.append(carry);
        return sb.reverse().toString();
    }
}


发表于 2021-02-01 14:57:29 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s1, s2;
    cin>>s1>>s2;
    int n=s1.size(), m=s2.size(), k;
    string r(n+m,'0');
    for(int i=n-1;i>=0;i--){
        int c = 0;
        for(int j=m-1;j>=0;j--){
            int t = (r[i+j+1]-'0') + (s1[i]-'0')*(s2[j]-'0') + c;
            r[i+j+1] = t%10 + '0';
            c = t/10;
        }
        r[i] += c;
    }
    for(k=0;k<r.size();k++)
        if(r[k]!='0')
            break;
    r = r.substr(k);
    cout<<r<<endl;
    return 0;
}

发表于 2020-11-10 01:10:00 回复(0)
from functools import reduce
def multiply(num1, num2):
    n1, n2 = len(num1), len(num2)
    if n1 < n2: num1, num2, n1, n2 = num2, num1, n2, n1
    res = []
    for j in range(n2 - 1, -1, -1):
        tmpRes = ''
        carry = 0
        for i in range(n1 - 1, -1, -1):
            tmp = int(num1[i]) * int(num2[j]) + carry
            tmpRes = str(tmp % 10) + tmpRes
            carry = tmp // 10
        tmpRes = str(carry) + tmpRes if carry != 0 else tmpRes
        if int(tmpRes) != 0:
            tmpRes += (n2 - j - 1) * '0'
        else:
            tmpRes = '0'
        res.append(tmpRes)
    return reduce(addStrings, res) if len(res) > 1 else res[0]

def addStrings(num1, num2):
    i, j, res = len(num1) - 1, len(num2) - 1, ''
    carry = 0
    while i >= 0&nbs***bsp;j >= 0&nbs***bsp;carry:
        c1 = int(num1[i]) if i >= 0 else 0
        c2 = int(num2[j]) if j >= 0 else 0
        tmp = c1 + c2 + carry
        carry = tmp // 10
        res = str(tmp % 10) + res
        i, j = i - 1, j - 1
    return res

a, b = input().split()
print(multiply(a, b))

发表于 2020-07-15 16:24:50 回复(0)
import java.math.BigDecimal;
import java.util.*;
public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner cin=new Scanner (System.in);
        String s1=cin.next();
        String s2=cin.next();
        BigDecimal b1=new BigDecimal(s1);
        BigDecimal b2=new BigDecimal(s2);
        BigDecimal b3=b1.multiply(b2);
        String s3=String.valueOf(b3);
        System.out.print(s3);

    }

}



发表于 2020-01-10 12:32:45 回复(0)
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

void output(vector<int> v)
{
    for (auto ele : v)
    {
        cout << ele;
    }
    putchar(10);
}

vector<int> mul(string x, string y)
{
    vector<int> res(x.length() + y.length(), 0);
    reverse(x.begin(), x.end());
    reverse(y.begin(), y.end());
    //先乘,不用考虑进位,int范围21亿,10以内的乘法,可以存2千万次
    for (int i = 0; i < x.length(); i++)
    {
        for (int j = 0; j < y.length(); j++)
        {
            //和x的第一位数乘,结果从res[0]开始保存,和x的第二位数乘,结果从res[1]开始保存,以此类推
            res[i + j] += (x[i] - '0') * (y[j] - '0');
        }
    }
    //最后一次性进位
    for (int i = 0; i < res.size() - 1; i++)
    {
        res[i + 1] += res[i] / 10;
        res[i] %= 10;
    }
    //3 * 3 = 9,但是申请了2个int的vector,最后一个int没有进位,pop掉
    while (res.back() == 0)
    {
        res.pop_back();
    }
    //逆置就是结果了
    reverse(res.begin(), res.end());
    return res;
}

int main()
{
    string x, y;
    while (cin >> x >> y)
    {
        output(mul(x, y));
    }
    return 0;
}

发表于 2019-08-19 18:42:16 回复(0)
a, b = map(int, input().split())
print(str(a*b))
发表于 2019-08-06 23:14:30 回复(0)