高精度减法的OP写法
stone_juice石汁
2019-08-08 09:53:13
## 高精度减法基础
- **[$\text{Blog}$ 阅读](https://www.luogu.org/blog/stonejuice/solution-p2142)**
- **[题解界面阅读](https://www.luogu.org/problemnew/solution/P2142)**
# 高精度减法的 $\text{OP}$ 写法
- ## 多重运算连击
通常来说，我们都是把高精度算法**写在了 $\text{main}$ 函数里面。**
**优点显而易见，这样写：直观，方便，写法简单，容易上手。**
但是，在面对下面这种情况，这样写就有点难受了。
如果一道题目里，**要求你进行多次高精度运算**，怎么办？
例如 $\text{a-b-c-d-.....}$
这个时候，如果依然按照“简单写法”，先算 $\text{a-b}$ ，然后 $\text{b-c......}$ **这样写码量惊人，而且很容易出错。“简单写法”并不再简单。**
这时候，我们可以进一步思考。**既然需要多次运算，我们可以考虑直接写个高精度运算子函数，每次运算只需要调用即可。**
这也是我比较推荐的做法。毕竟很少有题直接考高精度，通常高精度都是辅助工具，多次运算在所难免。
**那么我们现在就来了解下这种做法：子函数中写高精度！**
- ## 更加便捷的操作
既然我们要写子函数，那么必然会有返回值。
**这里可能有些人就犯难了，这个子函数究竟返回什么好？**
有些人可能会想到返回数组。但是不知道怎么写。
其实返回数组是可以的，当然，你不可能定义一个数组型变量(shenmegui)。**取之而代的，你可以定义返回一个指针。因为指针在某些情况下确实可以当成数组使用。** 利用指针传数组的值，也不是不可以。
**但是！我并不喜欢用指针。**
- 首先：指针是个强大的东西，但是就是因为它过于强大，所以经常指针会爆掉。爆空间越界一事那是经常发生，有时候莫名其妙就炸了也不是不可能。
- 第二：指针真的很不友好，知识点太多了，用不好就很容易出错。加上刚刚提到的那点，除非你用指针很小心，否则真的容易炸。
- ~~第三，因为我不会（迫真）~~
所以，我更加推崇**字符串**。**因为我们输入的时候就是采用输入字符串的形式。把字符串放进子函数处理，再返回出来一个答案字符串，对于我们来说更加友好易懂方便。**
于是我们定义一个 $\text{string}$ 型的字符串。
```cpp
string _minus(string a, string b)
{
//代码
}
```
这样，如果要输出，我们直接输出 _$\text{minus(a, b)}$ 即可。如果要重复运算也无妨，**反正我们输进去是字符串形式，输出也是字符串，输出的字符串可以马上又作为下次运算的输入，没有繁琐的形式转化，完全可以应对复杂的处理。**
那么这个子函数怎么写？
首先，我们所有的运算都是在子函数中进行的。**在可能有多次运算的情况下，我们不选择把数组开成全局变量**（开在函数外），开在外面共用数组可能会导致数字重复混淆。
**当然你可以用开更多数组解决问题，但是既然这样，为何我们不选择开在函数内呢？**
我先把代码扔下来：
```cpp
#include<bits/stdc++.h>
#define mian main
#define QWQ puts("QWQ");
#define MAXN 10500
using namespace std;
string a, b;
string _minus(string a, string b)
{
int na[MAXN] = {0}, nb[MAXN] = {0}, ans[MAXN] = {0};
string diff;
if((a < b && a.size() <= b.size()) || b.size() > a.size())
return "-" + _minus(b, a);
for(int i = a.size(); i > 0; i --)na[i] = a[a.size() - i] - '0';
for(int i = b.size(); i > 0; i --)nb[i] = b[b.size() - i] - '0';
int maxl = max(a.size(), b.size());
for(int i = 1; i <= maxl; i ++)
{
if(na[i] < nb[i])
{
na[i + 1] --;
na[i] += 10;
}
ans[i] = na[i] - nb[i];
}
while(ans[maxl] == 0)maxl --;//防止减后降位，多输出若干0
if(maxl < 1)return "0";
for(int i = maxl; i > 0; i --)diff += ans[i] + '0';//数组转化为字符串。
return diff;
}
int main()
{
cin >> a >> b;
cout << _minus(a, b);
return 0;
}
```
**可以看到：绝大多数，包括核心相减代码都没有变。**
我们重点看下变化的部分。
**$1$、 数组**
显而易见，我们把数组开在了里面。**开在里面和开在全局变量有些不同，全局变量里的每个空间存的数默认为 $0$，但我不知道开在子函数里会不会影响，所以我还是初定义了一下。**
**如果写出 $\text{a[MAXN]=0}$，意思就是把 $\text{a}$ 数组中的全部数设为 $0$。** 这好像是 $0$ 的特殊福利，因为如果是其他数，例如 $\text{a[MAXN]=1}$，$\text{a}$ 数组只会把 $\text{a[0]}$ 设为 $1$。
我们可以用已经定义好的数组继续运算。
**$2$、 字符串与返回值**
由于我们函数设定的 $\text{string}$ 类，所以返回值也必须是 $\text{string}$。
所以，我们在最后进行运算时，把普通的输出改成了**数组转化为字符串。**
呐，就是这句话：
```cpp
string diff;//已经在子函数最上方定义
for(int i = maxl; i > 0; i --)diff += ans[i] + '0';//数组转化为字符串。
return diff;
```
**这句话的意思是，每次循环，就把 $\text{a[i]}$ 转化为字符加到 $\text{diff}$ 字符串的末尾。**
我们把字符转化为数字时，由于 $\text{ASCII}$ 码的存在，所以要减去 $48$ 或 $\text{'0'}$。**同理，数字转化为字符也需要加上 $48$ 或 $\text{'0'}$**。
最后，答案数组中的全部数字转化为字符，存在 $\text{diff}$ 字符串中，直接返回出去。
**$3$、$\text{b>a}$ 与 $\text{a-b=0}$ 的新写法**
我们已经知道，在 $\text{b>a}$ 和 $\text{a-b=0}$ 这两种情况是要特判的。
**①先聊聊 $\text{b>a}$** 。我们一般处理方法是交换两数，在相减后最后在答案前打个负号。
交换两数目的是什么，无非就是把 $\text{a-b}$ 变为 $\text{b-a}$。
我们现在就不用这种麻烦的方法了，我们现在有逼格十足的子函数！
既然你想要 $\text{b-a}$，行，子函数调用一遍 _$\text{minus(b, a)}$。在前面打上负号，直接 $\text{return}$ 返回。
大概就是这么写：
```cpp
if((a < b && a.size() <= b.size()) || b.size() > a.size())
return "-" + _minus(b, a);
```
是不是比原来方便了很多？
**②再论 $\text{a-b=0}$。** 这个就很简单了，判断成立直接返回 $0$ 即可，和原来的方法也相差无几
```cpp
if(maxl < 1)return "0";
```
完整代码就是这个了：
```cpp
#include<bits/stdc++.h>
#define mian main
#define QWQ puts("QWQ");
#define MAXN 10500
using namespace std;
string a, b, c, d;
string _minus(string a, string b)
{
int na[MAXN] = {0}, nb[MAXN] = {0}, ans[MAXN] = {0};
string diff;
if((a < b && a.size() <= b.size()) || b.size() > a.size())
return "-" + _minus(b, a);
for(int i = a.size(); i > 0; i --)na[i] = a[a.size() - i] - '0';
for(int i = b.size(); i > 0; i --)nb[i] = b[b.size() - i] - '0';
int maxl = max(a.size(), b.size());
for(int i = 1; i <= maxl; i ++)
{
if(na[i] < nb[i])
{
na[i + 1] --;
na[i] += 10;
}
ans[i] = na[i] - nb[i];
}
while(ans[maxl] == 0)maxl --;//防止减后降位，多输出若干0
if(maxl < 1)return "0";
for(int i = maxl; i > 0; i --)diff += ans[i] + '0';//数组转化为字符串。
return diff;
}
int main()
{
cin >> a >> b >> c >> d;
cout << _minus(a, b) << endl;//直接调用
cout << _minus(b, c) << endl;
cout << _minus(c, d);
//可以看到，这里不管算多少次，调用一下即可，非常方便
return 0;
}
```
- ## $100\%$ 数据满足 $-10^{10086} \le a,b \le 10^{10086}$
现在还有一个小小的拓展问题。
**我们之前提到的“简单高精度”，它的数据范围并没有涉及 $a,b < 0$ 的情况。一旦 $a,b$ 出现负数，那么我们又无法处理了。**
这时候，我们就需要**借助高精度加法!**
为什么高精度加法也掺和进来了.........
我们分$3$种情况讨论
- 1、$a < 0 , b > 0$ 这种情况下，$-a > 0$ ，所以我们擦去 $a$ 的负号，并使用 $-a$ 运算，于是就有 ： $- a - b = - (a + b)$
- 2、$a > 0 , b < 0$ 这种情况下，$-b > 0$ ，所以我们擦去 $b$ 的负号，并使用 $-b$ 运算，于是就有 ： $a - (-b) = a + b$ （同上）
- 3、$a < 0 , b < 0$ 这种情况下，$-a > 0, -b > 0$ ，所以我们擦去 $a,b$ 的负号，并使用 $-a, -b$ 运算，于是就有 ： $- a - (-b) = b - a$
有些人可能会说：使用 $-a, -b$ 运算连正负都改变了，算出来肯定是错的啊？
其实不然。**我们之前已经擦去了 $a, b$ 的负号，也就是说我们已经把正负换过一遍了。** 运算的时候我们不过换回来了而已。
可以看到，要解决上面三种情况，其中 $1,2$ 情况都需要借助高精度加法。
**假设 _$\text{add(a, b)}$ 是高精度相加函数，上述情况可以这样写：**
```cpp
string a,b;
cin>>a>>b;
if(a[0]=='-'&&b[0]=='-') //当两个数字为负数
{
a.erase(0,1);
b.erase(0,1);//擦掉a,b打头的负号再运算，下同
cout<<_minus(b,a); //-a-(-b)=-a+b=b-a
return 0;
}
else if(a[0]=='-') //只有a为负数
{
a.erase(0,1);
cout<<"-"<<_add(a,b); //-a-b=-(a+b)
return 0;
}
else if(b[0]=='-') //只有b为负数
{
b.erase(0,1);
cout<<_add(a,b); //a-(-b)=a+b
return 0;
}
else cout<<_minus(a,b);
```
**当然，刚刚写的东西都是放在主函数里的。** 其实可以写的更简便，代码更短，但是这样分层写要好理解一些。
**顺带一提，$\text{a.erase(0,1);}$ 是字符串的一种语句，作用是把 $\text{a[0]}$ 的那个字符消掉。如果为负，自然那个符号就是负号了。$\text{b}$ 也是同理。**
而且，**上面介绍的把运算开在子函数里也帮了我们大忙**，可以在代码中看出来，可谓是方便快捷。
高精度加法我就不赘述了，方法其实和减法一样，竖式运算，只不过要注意最大位进位而已，其他就没什么好说的了。
**于是，我们现在有了一个究极 $\text{AC}$ 代码。**
- ## 究极代码横空出世了！
```cpp
#include<bits/stdc++.h>
#define mian main
#define QWQ puts("QWQ");
#define MAXN 10500
using namespace std;
string a, b;
string _add(string a, string b)//高精度相加 (为底下a或b为负数相减做铺垫)这个都会吧。
{
string sum;
int na[MAXN] = {0}, nb[MAXN] = {0}, ans[MAXN + 1] = {0};
for(int i = a.size(); i > 0; i --)na[i] = a[a.size() - i] - '0';
for(int i = b.size(); i > 0; i --)nb[i] = b[b.size() - i] - '0';
int maxl = max(a.size(), b.size());
for(int i = 1; i <= maxl; i ++)
{
ans[i + 1] = (ans[i] + na[i] + nb[i]) / 10;
ans[i] = (ans[i] + na[i] + nb[i]) % 10;
}//相加
if(ans[maxl + 1] != 0)sum += "1";//特判 防止最大位进位
for(int i = maxl;i > 0; i --)sum += ans[i]+'0';
return sum;
}
string _minus(string a, string b)
{
int na[MAXN] = {0}, nb[MAXN] = {0}, ans[MAXN] = {0};
string diff;
if((a < b && a.size() <= b.size()) || b.size() > a.size())
return "-" + _minus(b, a);
for(int i = a.size(); i > 0; i --)na[i] = a[a.size() - i] - '0';
for(int i = b.size(); i > 0; i --)nb[i] = b[b.size() - i] - '0';
int maxl = max(a.size(), b.size());
for(int i = 1; i <= maxl; i ++)
{
if(na[i] < nb[i])
{
na[i + 1] --;
na[i] += 10;
}
ans[i] = na[i] - nb[i];
}
while(ans[maxl] == 0)maxl --;//防止减后降位，多输出若干0
if(maxl < 1)return "0";
for(int i = maxl; i > 0; i --)diff += ans[i] + '0';//数组转化为字符串。
return diff;
}
int main()
{
string a,b;
cin >> a >> b;
if(a[0] == '-' && b[0] == '-') //当两个数字为负数
{
a.erase(0, 1);
b.erase(0, 1);//擦掉a,b打头的负号再运算，下同
cout << _minus(b,a); //-a-(-b)=-a+b=b-a
return 0;
}
else if(a[0] == '-') //只有a为负数
{
a.erase(0, 1);
cout << "-" << _add(a, b); //-a-b=-(a+b)
return 0;
}
else if(b[0] == '-') //只有b为负数
{
b.erase(0, 1);
cout << _add(a, b); //a-(-b)=a+b
return 0;
}
else cout << _minus(a, b);
return 0;
}
```
- ## 尾声
到这里，我要讲的也差不多讲完了。
这篇题解，前前后后码了有 $3$ 个小时，包括查资料和写框架。希望我的努力对大家有帮助。
欢迎大家指正错误，改良算法。
$\color{#FAFAFA}\colorbox{#FAFAFA}{当然也不排斥大家点赞哈哈哈}$
你们的支持是我最大的动力！
# [$\text{My Blog}$](https://www.luogu.org/blog/stonejuice/)