实现大数乘法，输入是两个字符串如
n1 = '340282366920938463463374607431768211456'
n2 = '340282366920938463463374607431768211456'
输出
'115792089237316195423570985008687907853269984665640564039457584007913129639936'
要求：不能使用对大数相乘有内建支持的语言；需要包含对输入字符串的合法性校验
[编程题]大数乘法
- 热度指数：4264 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
输入描述:
一行，两个非负整数n1,n2，保证|n1|+|n2|<10000，其中|n|是n作为字符串的长度
输出描述:
输出n1*n2的结果
示例1
输入
340282366920938463463374607431768211456 340282366920938463463374607431768211456
输出
115792089237316195423570985008687907853269984665640564039457584007913129639936
备注:
给出的数据均是合法的，但仍建议您对输入的字符串进行合法性校验
模拟竖式
string solve(string s, string t) {
int m=s.size(),n=t.size();
string result="0";
for(int i=m-1;i>=0;--i){
string cur="";
int carry=0;
for(int j=n-1;j>=0;--j){
int mul=(s[i]-'0')*(t[j]-'0')+carry;
cur=to_string(mul%10)+cur;
carry=mul/10;
if(j==0&&carry) cur=to_string(carry)+cur;
}
for(int j=0;j<m-i-1;++j){
cur=cur+"0";
}
result=strAdd(result,cur);
}
return result;
}
string strAdd(string s,string t){
int carry=0;
string result="";
for(int i=s.size()-1,j=t.size()-1;i>=0||j>=0||carry;--i,--j){
int x=i>=0?s[i]-'0':0;
int y=j>=0?t[j]-'0':0;
int sum =x+y+carry;
result=to_string(sum%10)+result;
carry=sum/10;
}
return result;
}
发表于 2021-08-09 20:07:57
回复(0)
能偷懒就用BigInteger，不然模拟竖式来计算真的……很伤身体
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.math.BigInteger;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] nums = br.readLine().trim().split(" ");
BigInteger num1 = new BigInteger(nums[0]);
BigInteger num2 = new BigInteger(nums[1]);
System.out.println(num1.multiply(num2).toString());
}
} 模拟竖式的代码如下 import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] nums = br.readLine().trim().split(" ");
System.out.println(multiply(nums[0], nums[1]));
}
private static String multiply (String num1, String num2) {
if(num1.equals("0") || num2.equals("0")) return "0";
String res = "0";
for(int i = num2.length() - 1; i >= 0; i --){
int carry = 0;
StringBuilder temp = new StringBuilder();
// 补0
for(int j = 0; j < num2.length() - 1 - i; j ++)
temp.append(0);
int n2 = num2.charAt(i) - '0';
for(int j = num1.length() - 1; j >= 0 || carry > 0; j --) {
int n1 = j < 0 ? 0 : num1.charAt(j) - '0';
temp.append((n1 * n2 + carry) % 10);
carry = (n1 * n2 + carry) / 10;
}
res = addStrings(res, temp.reverse().toString());
}
return res;
}
private static String addStrings(String num1, String num2) {
StringBuilder sum = new StringBuilder();
int carry = 0;
for(int i = num1.length() - 1, j = num2.length() - 1; i >= 0 || j >= 0 || carry > 0; i --, j --) {
int x = i < 0 ? 0 : num1.charAt(i) - '0';
int y = j < 0 ? 0 : num2.charAt(j) - '0';
sum.append((x + y + carry) % 10);
carry = (x + y + carry) / 10;
}
return sum.reverse().toString();
}
}
编辑于 2021-04-12 18:13:46
回复(0)
import java.util.*;
public class Main {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param s string字符串 第一个整数
* @param t string字符串 第二个整数
* @return string字符串
*/
private static final int MAXN = 200100;
private Complex[] x1 = new Complex[MAXN];
private Complex[] x2 = new Complex[MAXN];
private int[] sum = new int[MAXN];
StringBuffer sb = new StringBuffer();
private static final double pi = Math.acos(-1.0);
private static class Complex{
private double x;
private double y;
public Complex(double x,double y){
this.x = x;
this.y = y;
}
public Complex add(Complex o1,Complex o2){
return new Complex(o1.x+o2.x,o1.y+o2.y);
}
public Complex subtract(Complex o1,Complex o2){
return new Complex(o1.x-o2.x,o1.y-o2.y);
}
public Complex multiply(Complex o1,Complex o2){
return new Complex(o1.x*o2.x-o1.y*o2.y,o1.y*o2.x+o1.x*o2.y);
}
}
public void change(Complex[] y,int len){
int i,j,k;
for(i=1,j=len/2;i<len-1;i++){
if(i<j){
Complex tem =y[i];
y[i] = y[j];
y[j] = tem;
}
k = len/2;
while (j>=k){
j-=k;
k/=2;
}
if(j<k) j+=k;
}
}
public void fft(Complex[] y,int len,int on){
change(y,len);
for(int h=2;h<=len;h<<=1){
Complex wn = new Complex(Math.cos(-on*2*pi/h),Math.sin(-on*2*pi/h));
for(int j=0;j<len;j+=h){
Complex w = new Complex(1,0);
for(int k=j;k<j+h/2;k++){
Complex u = y[k];
Complex t = w.multiply(w,y[k+h/2]);
y[k] = u.add(u,t);
y[k+h/2] = u.subtract(u,t);
w = w.multiply(w,wn);
}
}
}
if(on==-1){
for(int i=0;i<len;i++)
y[i].x/=len;
}
}
public String solve (String s, String t) {
int len1 = s.length();
int len2 = t.length();
int len=1;
while (len<len1*2||len<len2*2)
len<<=1;
for(int i=0;i<len1;i++)
x1[i] = new Complex(s.charAt(len1-i-1)-'0',0);
for(int i=len1;i<len;i++)
x1[i] = new Complex(0,0);
for(int i=0;i<len2;i++)
x2[i] = new Complex(t.charAt(len2-i-1)-'0',0);
for(int i=len2;i<len;i++)
x2[i] = new Complex(0,0);
fft(x1,len,1);
fft(x2,len,1);
for(int i=0;i<len;i++)
x1[i] = x1[i].multiply(x1[i],x2[i]);
fft(x1,len,-1);
for(int i=0;i<len;i++)
sum[i] = (int)(x1[i].x+0.5);
for(int i=0;i<len;i++){
sum[i+1]+=sum[i]/10;
sum[i]%=10;
}
len = len1+len2-1;
while (sum[len]<=0&&len>0)
len--;
for(int i=len;i>=0;i--)
sb.append(sum[i]);
return sb.toString();
}
public static void main(String[] args){
String s;
String t;
Scanner scanner = new Scanner(System.in);
s = scanner.next();
t = scanner.next();
System.out.println(new Main().solve(s,t));
}
} FFT板子
发表于 2021-03-22 22:26:13
回复(0)
无力回天···········
/*
思路一：模拟乘法累加
按照乘法原理进行求解，将每一位相乘，
相加的结果保存到同一个位置，到最后才算进位。
3 2 5
X 9 8
-------------------------
(24)(16)(40)
(27)(18)(45)
-------------------------
(27)(42)(61)(40)
-------------------------
31 8 5 0
*/
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s1 = sc.next();
String s2 = sc.next();
//String s = "340282366920938463463374607431768211456";
char[] chars = s1.toCharArray();
int[] num1 = new int[s1.length()];
int k = 0;
for(char c:chars)
num1[k++] = Integer.parseInt(String.valueOf(c));
char[] chars2 = s2.toCharArray();
int[] num2 = new int[s2.length()];
k = 0;
for(char c:chars)
num1[k++] = Integer.parseInt(String.valueOf(c));
int[] res = new int[num1.length*2];
res = bigNumberMultiply(num1,num1);
for (int i=0;i<res.length;i++)
System.out.print(res[i]);
}
public static int[] bigNumberMultiply(int[] num1, int[] num2){
//分配空间，用来存储结果数字。num1 * num2 的结果长度肯定小于 num1+num2
int[] res = new int[num1.length + num2.length];
//先不考虑进位的问题，根据竖式的乘法运算，
//num1 的第i位 X num2的第j位，结果应该存放在第i+j的位置
for(int i=0; i<num1.length; i++){
for(int j=0; j<num2.length; j++){
//结果数组往后移一位(i+j+1)，为最高位进位留出空间
//
res[i+j+1] = res[i+j+1] + num1[i]*num2[j];
}
}
//单独处理进位问题
for(int k = res.length-1; k>0; k--){
if(res[k] > 10){
//进位
res[k-1] = res[k-1] + res[k]/10;
//当前位取个位数
res[k] = res[k]%10;
}
}
return res;
}
} 
发表于 2020-04-24 01:28:15
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
string a, b;
cin>>a>>b;
int n=a.length(), m=b.length();
int s[n+m];
memset(s, 0, sizeof(s));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
s[n+m-i-j-2] += (a[i]-'0')*(b[j]-'0');
for(int i=0,c=0;i<n+m;i++){
s[i] += c;
c = s[i]/10;
s[i] %= 10;
}
bool p = true;
for(int i=n+m-1;i>=0;i--){
if(p){
if(i && !s[i])
continue;
else{
p = false;
cout<<s[i];
}
}else
cout<<s[i];
}
cout<<endl;
return 0;
}
发表于 2020-01-16 01:53:19
回复(0)
//需要考虑的特殊用例是：输入字符串为0||输入的最高位有0||得数前面的0要省略
#include <bits/stdc++.h>
using namespace std;
string strmul(string a,string b){
if(a.empty()||b.empty()||a[0]=='0'&&a.size()==1||b[0]=='0'&&b.size()==1)
return "0";
string str(a.size()+b.size(),'0');
int index,len=str.size()-1;
for(int i=a.size()-1;i>=0;i--,len--){
index=len;
int up=0;
for(int j=b.size()-1;j>=0;j--,index--){
int ans=(a[i]-'0')*(b[j]-'0');
int temp=ans%10+up+str[index]-'0';
str[index]=temp%10+'0'; //保留个位
up=ans/10 + temp/10; //保留进位
}
if(up!=0)
str[index]=up+'0';
}
int k=0;
while(str[k]=='0')
k++;
return str.substr(k);
}
int main(){
string a,b;
cin>>a>>b;
cout<<strmul(a,b);
return 0;
}
发表于 2019-11-02 21:22:45
回复(0)
最普通的解法，以后再研究更简单的解法吧
#include<stdio.h>
#include<string.h>
#define LEN 10000
void reverse(int a[],int n);
void copy(const char *str,int a[]);
int main()
{
char str1[LEN];
char str2[LEN];
scanf("%s%s",str1,str2);
int a = strlen(str1);
int b = strlen(str2);
int arr1[LEN] = {0};
copy(str1,arr1);
int arr2[LEN] = {0};
copy(str2,arr2);
reverse(arr1,a);
reverse(arr2,b);
int res[LEN] = {0};
int i;
for(i = 0;i < a;++i){
for(int j = 0;j < b;++j){
res[i + j] += arr1[i] * arr2[j];
res[i + j + 1] += res[i + j] / 10;
res[i + j] %= 10;
}
}
for(i = LEN - 1;res[i] == 0 && i;--i);
for(;i >= 0;--i){
printf("%d",res[i]);
}
return 0;
}
void reverse(int a[],int n)
{
for(int i = 0,j = n - 1;i < j;++i,--j){
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
void copy(const char *str,int a[])
{
int i = 0;
while(*str){
a[i++] = *str - '0';
str++;
}
}
发表于 2019-10-04 14:35:49
回复(0)
Java 版本，参考了几位大佬的回答。
//package cn.practice.niuke;
import java.util.Scanner;
/**
* 大数相乘。
* 给出的数据均是合法的，但仍建议您对输入的字符串进行合法性校验
* 远远超出 longest.
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s1 = scanner.next();
String s2 = scanner.next();
// 先不做校验。
int sumLen = s1.length() + s2.length();
int[] res = new int[sumLen];
for(int i = 0; i< s1.length(); i++) {
int num1 = s1.charAt(s1.length() -1 - i ) - '0';
for(int j = 0; j< s2.length(); j++) {
int num2 = s2.charAt(s2.length() -1 - j) - '0';
res[i +j ] += num1 * num2;
}
}
for(int i = 0; i< res.length - 1; i++) {
if(res[i] >= 10) {
res[i+1] += res[i] / 10;
res[i] %= 10;
}
}
int i = res.length -1;
for(; i> 0 && res[i] == 0; i--) {} // 去除结果前面的 0
StringBuilder sb = new StringBuilder();
for(; i>=0; i--) {
sb.append(res[i]);
}
System.out.println(sb.toString());
}
}
发表于 2019-08-22 16:53:02
回复(2)
//就是手工模拟乘法，这里有一个技巧是，先不考虑进位的问题，等算完之后在再考虑进位的问题，这里为了方便，先将字符串进行反转
#include <iostream>
#include <vector>#include <algorithm>
#include <string>
using namespace std;
int main(int argc, char const *argv[])
{
string s1,s2;
while(cin>>s1>>s2){
reverse(s1.begin(),s1.end());
reverse(s2.begin(),s2.end());
vector<int> v(s1.size() + s2.size(),0);
for(int i=0;i<s1.size();i++){
for(int j=0;j<s2.size();j++){
v[i+j] += (s1[i] - '0') * ( s2[j] - '0' );
}
}
for(int i=0;i<v.size() - 1;i++){
if(v[i] >= 10){
v[i+1] += v[i] /10;
v[i] %= 10;
}
}
string res;
int i;
for(i=v.size()-1;i>0 && v[i] == 0;i--)
;
for(;i>=0;i--){
res += (char)(v[i] + '0');
}
cout<<res<<endl;
}
system("pause");
return 0;
}
编辑于 2019-07-10 15:39:18
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main()
{
string st1,st2;
cin>>st1;
cin>>st2;
int n = st1.size(),m = st2.size();
int a[n + m];
fill(a, a + n + m, 0);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
a[n + m - i - j - 2] += (st1[i] - '0') * (st2[j] - '0');
for (int i = 0; i < n + m - 1; ++i)
{
a[i + 1] += a[i] / 10;
a[i] %= 10;
}
int r = n + m - 1;
for (; r && !a[r]; r--);
for (;r >= 0;--r)
cout<<a[r];
cout<<endl;
return 0;
}
发表于 2019-07-10 19:46:08
回复(1)
在遍历过程中递归判断进位，速度比倒数第二慢了一倍...
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void carry_bit(char *res, int k){
if(res[k]>9){
res[k-1] += res[k]/10;
res[k] %=10;
carry_bit(res, k-1);
}
}
int main() {
char s[10000], *n1, *n2;
n1 = s;
scanf("%s", n1);
n2 = n1 + strlen(s) + 1;
scanf("%s", n2);
int len_n1 = strlen(n1), len_n2 = strlen(n2);
int len_s = len_n1 + len_n2, temp_index;
char *res = (char*)malloc(sizeof(char)*(len_s+1));
memset(res, 0, sizeof(char)*(len_s+1));
// for(int i=0;i<len_s;i++) res[i] = 0;
res[len_s] = '\0';
for(int i=0; i<len_n1; i++) n1[i]-='0';
for(int i=0; i<len_n2; i++) n2[i]-='0';
for(int i=len_n1-1;i>=0;i--){
for(int j=len_n2-1;j>=0;j--){
temp_index = i+j+1;
res[temp_index] += n1[i]*n2[j];
carry_bit(res, temp_index);
}
}
for(int i=0; i<len_s; i++) res[i] += '0';
for(int i=0;i<len_s;i++){
if(res[i]!='0'){
printf("%s", res+i);
return 0;
}
}
printf("0");
return 0;
}
发表于 2024-01-26 19:19:28
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String a = sc.next();
String b = sc.next();
char[] large = null;
char[] small = null;
if(a.length() >= b.length()){
large = a.toCharArray();
small = b.toCharArray();
}else{
large = b.toCharArray();
small = a.toCharArray();
}
int[] mult = new int[a.length()+b.length()];
for(int j = small.length-1;j>=0;j--){
for(int i = large.length-1;i>=0;i--){
int num1 = small[j]-'0';
int num2 = large[i]-'0';
mult[large.length-1-i+small.length-1-j] += num1*num2;
}
}
for(int i=0;i<mult.length-1;i++){
if(mult[i]>9){
mult[i+1]+=mult[i]/10;
mult[i]%=10;
}
}
StringBuilder builder = new StringBuilder();
for(int i = mult.length-1;i>=0;i--){
builder.append(mult[i]);
}
String res = builder.toString();
for(int i = 0;i<res.length();i++){
if(res.charAt(i)!='0'){
res = res.substring(i);
break;
}
if(i==res.length()-1 && res.charAt(i) == '0'){
res = "0";
}
}
System.out.println(res);
}
}
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String a = sc.next();
String b = sc.next();
char[] large = null;
char[] small = null;
if(a.length() >= b.length()){
large = a.toCharArray();
small = b.toCharArray();
}else{
large = b.toCharArray();
small = a.toCharArray();
}
int[] mult = new int[a.length()+b.length()];
for(int j = small.length-1;j>=0;j--){
for(int i = large.length-1;i>=0;i--){
int num1 = small[j]-'0';
int num2 = large[i]-'0';
mult[large.length-1-i+small.length-1-j] += num1*num2;
}
}
for(int i=0;i<mult.length-1;i++){
if(mult[i]>9){
mult[i+1]+=mult[i]/10;
mult[i]%=10;
}
}
StringBuilder builder = new StringBuilder();
for(int i = mult.length-1;i>=0;i--){
builder.append(mult[i]);
}
String res = builder.toString();
for(int i = 0;i<res.length();i++){
if(res.charAt(i)!='0'){
res = res.substring(i);
break;
}
if(i==res.length()-1 && res.charAt(i) == '0'){
res = "0";
}
}
System.out.println(res);
}
}
发表于 2021-03-17 11:53:42
回复(0)
#include<cstdio>
(802)#include<cstring>
int main()
{
char str[10000];
int a[10000]={0},b[10000]={0};
scanf("%s",str);
int len1=strlen(str);
for(int i=0;i<len1;i++)
a[i]=str[len1-i-1]-'0';
scanf("%s",str);
int len2=strlen(str);
for(int i=0;i<len2;i++)
b[i]=str[len2-i-1]-'0';
int carry=0,i,c[10000]={0},s;
for(i=0;i<len1;i++)
{
s=i;
for(int j=0;j<len2;j++)
{
int temp=a[i]*b[j]+carry;
c[s]+=temp%10;
carry=temp/10;
if(c[s]>=10)
{
c[s]=c[s]%10;
carry++;
}
s++;
}
while(carry!=0)
{
c[s++]=carry%10;
carry=carry/10;
}
}
for(int j=s-1;j>=0;j--)
printf("%d",c[j]);
return 0;
} 这是为啥没输出了
编辑于 2020-04-03 16:44:47
回复(1)
function bitIntMultiply(num1, num2) {
num1 = toStringArray(num1);
num2 = toStringArray(num2);
let result = [];
// 乘数，假如为11
for (let i = 0; i < num1.length; i++) {
// 被乘数，假如为111，如将11的1与111的每一位相乘然后存入
for (let j = 0; j < num2.length; j++) {
// 将结果添加到对应的位数上，如果该位数上存在则继续加，不存在则写入
result[i + j] = result[i + j] ?
result[i + j] + num1[i] * num2[j] :
num1[i] * num2[j];
}
}
for (let i = 0; i < result.length; i++) {
// 确认是否进位，仅在进位时增加数组长度
let carry = Math.floor(result[i] / 10);
if (carry) {
result[i + 1] = result[i + 1] ?
result[i + 1] + carry :
carry;
}
result[i] = result[i] % 10;
}
return result.reverse().join('');
function toStringArray(num) {
return String(num).split('').reverse();
}
}
发表于 2019-12-30 15:37:57
回复(1)
可以通过93.3%，很不爽！
题目描述中讲，一行包括两个数，但提示的错误测试用例中只给出了一个数。。。题目还不说明这种情况输出什么。。。。猜不到100%呀！！
建议直接移步Leetcode：https://leetcode.com/problems/multiply-strings/
编辑于 2019-09-01 16:38:46
回复(1)
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string multiply(string num1, string num2) {
int len1 = num1.size(),len2 = num2.size();
string res(len1 + len2, '0');
for (int i = len2 - 1; i >= 0; i--) { //从个位开始。注意：数组是从高位到低位存储的，i+j相对i+j+1才是高位！
for (int j = len1 - 1; j >= 0; j--) {
int temp = (res[i + j + 1] - '0') + (num1[j] - '0')*(num2[i] - '0');//res[i + j + 1] - '0',有可能之前进位了，而且最多只会进位影响一位
res[i + j + 1] = temp % 10 + '0';//当前位.这里是等于，所以要加‘0’
res[i + j] += temp / 10; //前一位加上进位！！！res[i+j]已经初始化为'0'，加上int类型自动转化为char，所以此处不加'0'
}
}
//去除首位'0'
for (int i = 0; i<len1 + len2; i++) //从高位到低位找0
if (res[i] != '0')
return res.substr(i);//从第一个不是0的数截取
return "0";
}
int main() {
string num1,num2;
cin >> num1 >> num2;
cout << multiply(num1, num2)<<endl;
return 0;
}
编辑于 2019-08-13 21:36:56
回复(2)
Java似乎没法通过。。。。代码如下
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String big1 = sc.nextLine(); String big2 = sc.nextLine(); int length1 = big1.length(); int length2 = big2.length(); if (length1 == 0 && length2 == 0){ System.out.println("0"); } else { int[] res = new int[length1 + length2]; for (int i = 0; i < length1; i++) { int num1 = big1.charAt(length1 - 1 - i) - '0'; for (int j = 0; j < length2 ;j++) { int num2 = big2.charAt(length2 - 1 - j) - '0'; int tempres = num1 * num2; res[i + j] += tempres; } } for (int i = 0; i < length1 + length2; i++) { if (res[i] > 10){ res[i+1] += (res[i] / 10); res[i] %= 10; } } StringBuilder sb = new StringBuilder(); for (int i = length1 + length2 - 1; i >= 0 ; i--) { sb.append(res[i]); } System.out.println(Integer.parseInt(sb.toString())); } }
}
编辑于 2019-07-12 12:54:08
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-13 09:20:28 -
2022-09-09 16:23:24
-
2022-09-09 15:50:47 -
2022-09-06 16:32:47 -
2022-09-06 11:31:59
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
