首页 > 试题广场 >

大整数相乘

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

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


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

输入

72106547548473106236 982161082972751393

输出

70820244829634538040848656466105986748

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)
//写的不太好
#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)
N,M = input().strip().split()
print(eval(N) * eval(M))

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

发表于 2018-01-25 16:48:58 回复(0)
#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)
#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)
直接模拟乘法的竖式计算过程,不过要注意计算加法的时候数字排列是阶梯状的,需要在数的后面补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)
import java.util.Scanner;
import java.util.ArrayList;
import java.lang.Math;
public class Main{
    public static String add(String s1,String s2){
        int len1=s1.length();
        int len2=s2.length();
        int pad=Math.abs(len1-len2);
        String padding="";
        for(int i=0;i<pad;i++){
            padding=padding+"0";
        }
        if(len1>len2){
            s2=padding+s2;
        }else{
            s1=padding+s1;
        }
        
        int len=s1.length();
        
        String ans="";
        int c=0;
        for(int j=len-1;j>=0;j--){
            int a=s1.charAt(j)-'0';
            int b=s2.charAt(j)-'0';
            int v=(a+b+c)%10;
            c=(a+b+c)/10;
            ans=v+ans;
        }
        if(c>0){
            ans=c+ans;
        }
        return ans;
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            String s1=sc.next();
            String s2=sc.next();
            int len1=s1.length();
            int len2=s2.length();
            ArrayList<String> tmp=new ArrayList<>();
            for(int i=len2-1;i>=0;i--){
                String ans="";
                int v=s2.charAt(i)-'0';
                for(int j=0;j<v;j++){
                    ans=add(ans,s1);
                }
                int pad=len2-1-i;
                String padding="";
                for(int l=0;l<pad;l++){
                    padding=padding+"0";
                }
                ans=ans+padding;
                tmp.add(ans);
            }
            String result="";
            for(String s:tmp){
                result=add(result,s);
            }
            System.out.println(result);
        }
    }
}

发表于 2019-07-26 10:36:37 回复(2)
/*很朴素的代码*/
#include <iostream>
#include<string>
using namespace std;

int main()
{
    string str1,str2;
    cin>>str1>>str2;
    int s1=str1.size();
    int s2=str2.size();
    int *result=new int[s1+s2];
     for(int i=0;i<s1+s2;i++)
    {
       result[i]=0;
     }
    for(int i=s1-1;i>=0;i--)
    {
        int carry=0;
        for(int j=s2-1;j>=0;j--)
        {
            int temp=(str1[i]-'0')*(str2[j]-'0')+result[i+j+1]+carry;
            result[i+j+1]=temp%10;
            carry=temp/10;
            if(j==0)
                result[i]+=carry;
        }
    }
    int i = 0;
    while (result[i] == 0)
        i++;
    string s;
    for(i;i<s1+s2;i++) 
       s+=result[i]+'0';
    cout<<s<<endl;
    return 0;   
}

编辑于 2019-06-25 14:29:29 回复(0)
  • 仿照手算乘法的思路,逐位相乘,然后错位累加即可。
#include <bits/stdc++.h>
using namespace std;

string sum;

string multi(string str1, int num) {
    string tmp;
    int forward = 0;
    for (int i = str1.size() - 1; i >= 0; i--) {
        int s = num * (str1[i] - '0') + forward;
        tmp.insert(tmp.begin(), (s % 10) + '0');
        forward = s / 10;
    }
    if (forward)
        tmp.insert(tmp.begin(), forward + '0');
    return tmp;
}

string add(string s1, string s2) {
    int i = s1.size() - 1;
    int j = s2.size() - 1;
    int forward = 0;
    string tmp;
    while (i >= 0 && j >= 0) {
        int s = (s1[i] - '0') + (s2[j] - '0') + forward;
        tmp.insert(tmp.begin(), (s % 10) + '0');
        forward = s / 10;
        i--; j--;
    }
    while (i >= 0) {
        int s = (s1[i] - '0') + forward;
        tmp.insert(tmp.begin(), (s % 10) + '0');
        forward = s / 10;
        i--;
    }
    while (j >= 0) {
        int s = (s2[j] - '0') + forward;
        tmp.insert(tmp.begin(), (s % 10) + '0');
        forward = s / 10;
        j--;
    }
    if (forward)
        tmp.insert(tmp.begin(), forward + '0');
    return tmp;
}

int main(int argc, char const *argv[])
{
    string str1, str2;
    cin >> str1 >> str2;
    sum.clear();
    int flag = 1;
    //cout << "debug " << add("12", "12") << endl;
    for (int i = str2.size() - 1; i >= 0; i--) {
        string tmp = multi(str1, str2[i] - '0');
        //cout << tmp << endl;
        if (sum.empty())
            sum = tmp;
        else {
            //cout << "add is " << add(tmp, sum.substr(0, sum.size() - 1)) << endl;
            sum = add(tmp, sum.substr(0, sum.size() - flag)) + sum.substr(sum.size() - flag);
            flag++;
            //cout << "sum is " << sum << endl;
        }

    }
    cout << sum;
    return 0;
}
发表于 2019-06-25 11:00:58 回复(0)