import java.util.Scanner;
/**
Scanner scanner = new Scanner(System.in);
String num1 = scanner.next();
String num2 = scanner.next();
System.out.println(multiply(num1,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();
}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]))))
//写的不太好 #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; }
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(); } } } }
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);
N,M = input().strip().split()
print(eval(N) * eval(M))
一个用python答题者的心里过程:
为了显示我的能力,我表示我不用库函数都能写出来!
对着题思考十秒钟...
呵呵,这个库函数真好用
#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; }
# 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))
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
#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; }
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(); } }
#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; }
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))
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); } }
#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; }
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); } } }
/*很朴素的代码*/ #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; }
#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; }