洛谷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;
}