1.P1601 A+B Problem（高精）

题目解析：

由于是高精度的计算所以无法直接相加，需要先用字符串将数字存起来，后根据字符数字减去字符0可以转化为int类型来进行模拟列竖式进行加法

算法原理：

我们为了方便进行模拟我们在列竖式时的过程我们可以将原本的数反过来放入数组：

对应关系如上，写成代码：

int main()
{string s1,s2; cin>>s1>>s2;for(int i = 0;i<s1.size();i++) a[s1.size()-1-i] = s1[i] - '0';for(int i = 0;i<s2.size();i++) b[s2.size()-1-i] = s2[i] - '0';
}

再将主要逻辑写出来：

int main()
{string s1,s2; cin>>s1>>s2;la = s1.size(); lb = s2.size();lc = max(la,lb); for(int i = 0;i<s1.size();i++) a[s1.size()-1-i] = s1[i] - '0';for(int i = 0;i<s2.size();i++) b[s2.size()-1-i] = s2[i] - '0';add();for(int i = lc - 1;i>=0;i--) cout<<c[i]; return 0;
}

这里lc为相加后的长度，先直接取为两数的最大值，后续再根据结果进行判断：如果最前面不为0就lc++

模拟列竖式：

可以将进位直接放入到数组的前一位，直接相加后，进行进位和留余操作即可

最后判断最前方是否有数，如果有就将lc向前一位

代码如下：

#include <iostream>
using namespace std;
const int N = 1e6+10;
int a[N],b[N],c[N];
int la,lb,lc;void add()
{for(int i = 0;i<lc;i++){c[i] += a[i]+b[i];//一定是+=将进行的数加上c[i+1] = c[i]/10; //进位 c[i] %= 10; 	  //留余 }//处理前置数if(c[lc]) lc++; 
}

代码实现

#include <iostream>
using namespace std;
const int N = 1e6+10;
int a[N],b[N],c[N];
int la,lb,lc;void add()
{for(int i = 0;i<lc;i++){c[i] += a[i]+b[i];c[i+1] = c[i]/10;//进位 c[i] %= 10; 	 //留余 }//处理前置数if(c[lc]) lc++; 
}
int main()
{string s1,s2; cin>>s1>>s2;la = s1.size(); lb = s2.size();lc = max(la,lb); for(int i = 0;i<s1.size();i++) a[s1.size()-1-i] = s1[i] - '0';for(int i = 0;i<s2.size();i++) b[s2.size()-1-i] = s2[i] - '0';add();for(int i = lc - 1;i>=0;i--) cout<<c[i]; return 0;
}

2.P2142 高精度减法 - 洛谷

算法原理

和之前一样需要先将字符串导致存放到数组中方便运算，但是减法和加法 有一个本质的区别就是：

减法需要用大数字减去小数字这样我们可以直接进行比较，然后交换两者数据，一旦交换直接在前面输出一个-

即可直接进行大数减小数

1. 交换数据

   • 根据字符串长度来判断
   • 字符串长度一样可以根据字符串直接进行比较

   bool my_swap(string &s1,string &s2)
   {if(s1.size()!=s2.size()) return s1.size()<s2.size();else return s1<s2;
   }int main()
   {string s1,s2; cin>>s1>>s2;if(my_swap(s1,s2)){swap(s1,s2);cout<<'-';}
   }
   

2. 和加法一样将字符串倒置方便后续计算

   #include <iostream>
   using namespace std;const int N = 1e6+10;
   int la,lb,lc;
   int a[N],b[N],c[N];
   int main()
   {string s1,s2; cin>>s1>>s2;if(my_swap(s1,s2)){swap(s1,s2);cout<<'-';}la = s1.size();lb = s2.size();lc = max(la,lb);for(int i = 0;i<la;i++) a[i] = s1[la-1-i] - '0';for(int i = 0;i<lb;i++) b[i] = s2[lb-1-i] - '0';
   }
   

3. 减法的逻辑

   • 直接进行减法
   • 如果不够进行借数
   • 如果前面的数字相减为0,就需要处理前置0

   void sub()
   {for(int i = 0;i<lc;i++){c[i] += a[i] - b[i];//直接进行减法if(c[i]<0)//如果不够进行借数{c[i] += 10;c[i+1] -= 1;}}while(c[lc-1]==0&&lc>1) lc--;//前置0
   }
   

   这里要注意lc > 1不要访问越界

   

代码实现

#include <iostream>
using namespace std;const int N = 1e6+10;
int la,lb,lc;
int a[N],b[N],c[N];bool my_swap(string &s1,string &s2)
{if(s1.size()!=s2.size()) return s1.size()<s2.size();else return s1<s2;
}void sub()
{for(int i = 0;i<lc;i++){c[i] += a[i] - b[i];if(c[i]<0){c[i] += 10;c[i+1] -= 1;}}while(c[lc-1]==0&&lc>1) lc--;
}
int main()
{string s1,s2; cin>>s1>>s2;if(my_swap(s1,s2)){swap(s1,s2);cout<<'-';}la = s1.size();lb = s2.size();lc = max(la,lb);for(int i = 0;i<la;i++) a[i] = s1[la-1-i] - '0';for(int i = 0;i<lb;i++) b[i] = s2[lb-1-i] - '0';sub();for(int i = lc-1;i>=0;i--) cout<<c[i];return 0;
}

3.P1303 A*B Problem - 洛谷

算法原理

1. 乘法逻辑

   如果我们直接进行进位就会让这道题变得复杂,但是如果我们现将要加的数字先直接加到数组中,接着在按照加法的逻辑进行相加就会让这道题简单不少

   • 找到相加的规律(c[i+j] += a[i]*b[j])

     

   • 进行进位

   • 处理前置0

   void mul()
   {for(int i = 0;i<la;i++){for(int j = 0;j<lb;j++){c[i+j] += a[i]*b[j];}}for(int i = 0;i<lc;i++){c[i+1] += c[i] / 10;c[i] %= 10;}while(lc>1&&c[lc-1]==0) lc--;
   }
   

2. 再将主函数进行补齐

   int main()
   {string s1,s2; cin>>s1>>s2;la = s1.size();lb = s2.size();lc = la+lb;for(int i = 0;i<la;i++) a[i] = s1[la-i-1] - '0';for(int i = 0;i<lb;i++) b[i] = s2[lb-i-1] - '0';mul();for(int i = lc-1;i>=0;i--) cout<<c[i];return 0;
   }
   

代码实现

#include <iostream>
using namespace std;const int N = 1e6+10;
int a[N],b[N],c[N];
int la,lb,lc;void mul()
{for(int i = 0;i<la;i++){for(int j = 0;j<lb;j++){c[i+j] += a[i]*b[j];}}for(int i = 0;i<lc;i++){c[i+1] += c[i] / 10;c[i] %= 10;}while(lc>1&&c[lc-1]==0) lc--;
}
int main()
{string s1,s2; cin>>s1>>s2;la = s1.size();lb = s2.size();lc = la+lb;for(int i = 0;i<la;i++) a[i] = s1[la-i-1] - '0';for(int i = 0;i<lb;i++) b[i] = s2[lb-i-1] - '0';mul();for(int i = lc-1;i>=0;i--) cout<<c[i];return 0;
}

4.P1480 A/B Problem - 洛谷

算法原理

这里不是两个数都是高精度,仅仅只有被除数是高精度,而除数为longlong类型即可,这道题需要注意int类型是否越界

1. 除法原理

   • 我们需要创建一个变量来保存上一位的余数,而对于下一位的我们需要将上一位的余数*10+下一位的原本的数字再去执行除法逻辑即可

   void sub()
   {long long ret = 0;for(int i = la-1;i>=0;i--){a[i] += ret*10;c[i] = a[i] / n;ret = a[i]%n;}while(lc>1&&c[lc-1]==0) lc--;
   }
   

2. 其他的部分与上面差不多(要注意int的范围,不要数据让数据丢失)

   #include <iostream>
   using namespace std;
   const int N = 1e6+10;
   long long a[N],c[N];
   int la,lc;
   long long n;int main()
   {string s; cin>>s;cin>>n;la = s.size();lc = la;for(int i = 0;i<la;i++) a[i] = s[la-i-1] - '0';sub();for(int i = lc-1;i>=0;i--) cout<<c[i];return 0;
   }
   

代码实现

#include <iostream>
using namespace std;
const int N = 1e6+10;
long long a[N],c[N];
int la,lc;
long long n; void sub()
{long long ret = 0;for(int i = la-1;i>=0;i--){a[i] += ret*10;c[i] = a[i] / n;ret = a[i]%n;}while(lc>1&&c[lc-1]==0) lc--;
}
int main()
{string s; cin>>s;cin>>n;la = s.size();lc = la;for(int i = 0;i<la;i++) a[i] = s[la-i-1] - '0';sub();for(int i = lc-1;i>=0;i--) cout<<c[i];return 0;
}