洛谷P1303高精度A×B

发表于

1. 题目描述

求两数的积。每个数字不超过10的2000次方，需用高精。

2. Notes

  1. 本题模拟的是竖式乘法运算，算出每一位与大数的乘积再错位相加。

  2. 竖式乘法的原理：
    比如12345×1234=12345×(1000+200+30+4)，我们平时列竖式的时候只是把最后几位的0省去了。这样就将两个大数相乘转化为一个大数乘以一个一位数字再相加。

  3. 用string类对象赋值时要注意的地方

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
      string str[10]; //定义一个10个大小的string对象数组
      str[1][0]='a'; 
      /*
    按上述方法赋值，str[1]这个字符串第一个字符不是a，输出str[1]为空串
      因为str[1][0]这个位置还没有分配，所以为空
      若想赋值按下述方法对str[1]这个字符串级别的变量进行赋值
      不要对还没分配空间的字符字符级别进行赋值（如此处的str[1][0]）
      */
      str[1].append("a");
      str[1]=str[1]+'a';

  4. 高精乘思路：

    1. $a,b$中有0直接返回0，否则将$a,b$倒置。
    2. 模拟竖式乘法，假设$a$在上方，$b$在下方，用$b$的每一位与$a$相乘再加上来自低位的进位，取余取整分别作为该位的值和进位。
    3. $b$的中的一位与$a$中每一位乘完仍然有可能有进位，记得检验。（乘法中每一位的进位不超过9）。
    4. 按照当前$b$中数字所在的位数进行补0。
    5. 调用高精加求和即可。

3. 题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;

string add(string a,string b); //高精度加法由P1601得、略微修改
 
int main(){
	string a,b,result;
	int m,n,carry,i,j,k,p;
	cin>>a>>b;
	if(a[0]=='0' or b[0]=='0'){
		cout<<0;
	}else{  //最高位不为0，结果最高位一定不为0
		reverse(a.begin(),a.end());
		reverse(b.begin(),b.end());
		m=a.length();
		n=b.length();
		string sv[n];
		carry=0;
		for(i=0;i<n;i++){
			for(j=0;j<m;j++){
				p=(int)(a[j]-'0')*(int)(b[i]-'0');
				p+=carry;
				sv[i]=sv[i]+(char)((p%10)+'0');
				carry=p/10;
			}
            if(carry>0){
	        	sv[i]=sv[i]+(char)(carry+'0');
			}
			for(k=0;k<i;k++){
				sv[i]='0'+sv[i];	
			}
		}
		result=sv[0];
		for(i=1;i<n;i++){
			result=add(result,sv[i]);
		}
	
		reverse(result.begin(),result.end());
		cout<<result;
	}
	return 0;
} 

string add(string a,string b){
	int m,n,i,tmp,carry;
	carry=0;
	m=a.length();
	n=b.length();
	if(m>n){
		for(int j=0;j<(m-n);j++){
			b=b+'0';
		}
	}else if(n>m){
		for(int j=0;j<(n-m);j++){
			a=a+'0';
		}
		m=n; //赋值语句看清位置 
	}
	
	for(i=0;i<m;i++){
		tmp=a[i]-'0'+b[i]-'0'+carry;
		carry=tmp/10;
		tmp=tmp%10;
		a[i]=(char)(tmp+'0');
	}
	if(carry>0){
		a=a+'1';
	}
	return a;
}