自动搬运

查看原文

来自洛谷，原作者为

	stone_juice石汁 敲稀有滴物种石汁qaq

搬运于2025-08-24 21:34:27，当前版本为作者最后更新于2018-11-18 17:51:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解 /【学习笔记】-- 高精度减法

修改日志：

• 1、19/3/31 修改：优化了批注，写的更易懂一些。

• 2、19/8/8 修改：增加了图片，细节更多，调整码风，解决了一些小BUG，科普了一些无关紧要的知识。（重大修改）

• 1、$int$的悲伤与高精度的需求。

  我们往常在作运算的时候，往往直接用运算符完成运算（譬如a - b）。这当然非常地简便。

  但是当数据范围特别大的时候，你去用运算符做减法往往得不到正确的结果，为什么？？

  首先，在$c++$里，每一种实数变量型都是有一个数据储存范围的。譬如$int$型，它的数据范围就为 $-2147483648 < int < 2147483647$，也就是 $-2^{31} < int < 2^{31} -1$。一旦你给一个int型变量存一个大于这个范围的数，它就会产生溢出，然后你存的数字会变成另外一个非常神奇的数字 。可以自己在线下试一试哦。

  不要和我提Py和java！

  这个时候，你存的数字本身就已经发生错误，就不用指望他来运算了。

  当然也有解决办法，譬如开$long long$。但是当数据范围高到恐怖的地步的时候（甚至大于$10^{1000}$），别说$long long$了，开挂神器__$int128$都救不了你。

  这个时候，就需要高精度算法来解决问题。

• 2、数组搞定高精度数字

  上面我们有提到过，在数据范围很大的时候，任何变量型已经无法满足我们的需求。这个时候怎么办？

  接下来介绍一种最传统的做法：开数组。

  我们开一个数组。这个数组开到多大？就要看你要存的数的位数有多少。若想存一个$2000$位的数，就把数组开到$2000$以上。

  你位数可以多啊，你多一位 位数，我就把数组多开一个空间。看谁斗得过谁

  而本题甚至开到了$10086$位，所以我选择把数组开到$10500$位。（开多点没坏处）

  想必这样说大概都清楚了。我们用数组的每一个空间来存每一位数的那个数字。

  这句话是什么意思呢？我们打个比方。

  比如说我们现在要存$123$这个数，把它存进$na$数组里。

  我们可以取出最后一位（个位）$3$，放到$na[1]$中。于是$na[1] = 3$

  同理，我们取出$2,1$放进数组，于是就有：

   na[1] = 3;
   na[2] = 2;
   na[3] = 1;
  
   //也就是: na[MAXN] = {3, 2, 1};
   
  

  此时，$na[i]$就代表了此数的最后$i$位

  但是

  我们并不选择直接一个一个输入每位数字，把数字存进数组。

  我们选择使用字符串 ，像这样：

  string a, b;
  cin >> a >> b;
  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';
  //这个代码底下有解释
  

  为什么这样做？

  首先，字符串输入两个数字，我们可以直接地知道每个数字的长度，也就是位数（字符串$a$的长度为$a.size()$，依次类推）。知道长度就可以直接给$for$循环服务。

  其次，字符串它输入方便啊，一个$cin$就完成了，也不必去检验什么输入到空格之类的了。

  当然，最方便的是可以将字符串扔进子函数里（这个在最后有拓展）

  当然：将字符串转化进数组需要一定技巧：

  1、首先，字符串里同样可以用下表形式表示某位的数（譬如$a[i]$），但是和我们之前的存法相反，$a[0]$ 表示的数字的最高位，次高位是$a[1]$。他是从$0$且是从高位算起的，和我们之前说的从低位开始存恰好相反。

  2、其次，字符串里每个数其实都是$char$型的。虽然看起来和$int$型没什么不同，但是想把$char$型转化成$int$型需要通过一个介质：$ASCII$码。

  每个$char$字符都有对应的$ASCII$码，而$0-9$的$ASCII$码是$48 - 57$。如果你尝试把一个$char$型的$0$存进$int$，那么存进去的则是$0$的$ASCII$码，也就是$48$。

  这两个情况怎么解决？

  • 1、第一个问题，我们只需要把数组的第$i$位和字符串的第（位数 $- i$）位对应起来就可以了。这是很好证明的。

  假设我们要存一个$3$位数，它的每一位：

  用数组表示：$na[1], na[2], na[3]$

  用字符串表示:$a[3 - 1], a[3 - 2], a[3 - 3]$（这里千万要注意字符串下标是从$0$开始存的，也就是$a[0]$表示最高位）

  代码中手打出来就可以了。

  • 2、第二个问题，$0-9$的$ASCII$码不是$48 - 57$么，那么把字符引入$int$型的时候，我们只需要引入时把每个数减去$48$就行了。 $48-57$减去$48 = 0-9$ 道理都懂，对吧。

  当然你可以把$48$写成$'0'$。$'0'$就代表着$0$的$ASCII$码

  于是这就有了我上面给出的代码：

   string a, b;
   cin >> a >> b;
  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';
   
  

  • 于是乎，我们就有了两个数组，存了两个高精度数字。

• 3、小学计算教你做减法

  数字存进数组去了，那么问题来了，如何让两个数组作减法？？

  答案很简单：小学竖式运算！

  什么？你居然教我减法用竖式？？？

  好吧，可能各位做减法熟能生巧，不需要列竖式就可以口糊出来。但是你要知道，计算机并不会做数组相减的运算。于是我们就需要“教他”算。

  小学老师怎么教你算减法？当然是竖式运算。

  具体做法就是：把两个数字的每一位对齐，从低位到高位，同一位逐次相减，如果减不够就向后一位借位。（小学竖式借位甚至还要向借的位打标记防止你忘了）

  计算机的竖式运算同样是这个道理。我们假设有两个存了数字的数组$na,nb$。

  我们把两个数的每位对齐，刚刚我们提到：$na[i]$代表$a$这个数的第$i$位。同理：$nb[i]$代表$b$这个数的第$i$位。

  那么，我们只需要做的就是$na[i] - nb[i]$就行了。这就代表了$a$的第$i$位减去了$b$的第$i$位

  我们用表格演示一下$456789$减去$135353$，其中，$ans$数组用来存储答案

  

  可以看到，每一位依次相减，最后传进答案数组，这个相减的过程就完成了。

  用代码表示，可以表示成：

  ans[i] = na[i] - nb[i];
  

  可是！以上问题没有考虑过借位的情况！

  如果要借位，我们怎么处理？？

  根据小学竖式的博大精深来看，我们可以向高位借位，然后再相减。

  这个借位如果要说明白点，就是高位减去一个$1$，给低位一个$10$加上然后再相减。

  具体的，如果运算$34 - 19$，$4 - 9$明显减不够，于是：

   34 - 19 = (30 + 4) - (10 + 9) = (20 + 14) - (10 + 9) 
   = (20 - 10) + (14 - 9) = 10 + 5 = 15
  

  上面的例子中，$30$很明显借了$10$给$4$，然后$14$ - $9$进行运算

  这个东西放到我们数组相减也适用。简单来说，当一位减不够另一位时，就从高位借$10$过来再减，当然，高位会比原来少$1$。

  我们再用表格举个例子：$456789 - 147791$

  

  这样就成功处理了减位的问题。

  用代码就这样表示：

   int maxl = max(a.size(), b.size());
   /*
   找到两个数中的最大位，为for循环服务 
   如果两个数位数不相等，相减也无妨，因为位数少的数那部分被0补齐，减下去不影响
   */
   for(int i = 1; i <= maxl; i ++)
   {
   	if(na[i] < nb[i])//减不够
   	{
   		na[i + 1] --;//借位
   		na[i] += 10;//到低位去
   	}
   	ans[i] = na[i] - nb[i];//相减
   }
  

  于是，相减代码就是这样了

• 4、看似已完成，输出却全是坑

  你以为这样就做完了？评测姬告诉你：Too Young Too Simple

  输出里还有一些坑，把你坑的头皮发麻。

  平常的输出方式是什么？我们现在知道了两个数的最大位，上面也有提到过。我们用$maxl$表示。

  因为我们是从个位，逐渐递增存每位上的信息，但是我们要从最高位开始输出，也就是我们要先输出最高位。 这倒是和字符串有点相似。

  于是我们采用倒着输出方法，代码大概是这个样子。

  for(int i = maxl; i > 0; i --)cout << ans[i];
  

  但是！坑来了。

  • 坑点1、

  如果你用$10001 - 10000$，会发生什么？

  当然你会知道它应该输出$1$。可你的计算机不这么认为。

  依照上面的输出方法，此时$maxl$为$5$。那么，它输出的就不是$1$，而是$00001$！，因为他会输出$maxl$次，也就是$5$次，并且是从$ans[5]$ 输到 $ans[1]$。但此时：$ans[2]-ans[5]$都已经为$0$

  所以我们不得不考虑，在相减后位数下降的情况下，不特殊处理就会多输出若干个$0$。

  解决方法很简单，输出前加上这么一句话即可：

  while(ans[maxl] == 0)maxl --;
  //如果最高位为0，就一直减小最高位，直到不为0为止。
  

  由于$maxl$直接为输出的$for$循环服务，减小$maxl$相当于减少了循环输出次数。最后，$ans[maxl]$会停留在第一个不为$0$的位置。

  • 坑点2、

  上面的坑点提到要去除多余的前导零，但是，是不是所有的前导零都是多余的？

  要是答案输出本身就为$0$，前导零就是他本身。这个时候我们仍然要输出一个$0$。 ，如果我们不处理这个地方，上面处理前导零的代码就会把需要输出的$0$也给处理掉。

  也就是说，当两减数相等，答案为$0$，不处理这个地方，代码什么都不会输出。

  所以我们要在最后输出时这么写：

   if(maxl < 1)cout << "0";
  //最大位小于1，也就是最高位为0时输出。
  //最高位为0，显而易见答案就为0了
  //这种情况下前面什么都不会输出，这里额外输出一个0倒也无伤大雅
  

  • 坑点3、

  这里还有一个坑，那就是：相减可能小于$0$

  显然，我们用上面的相减代码是处理不掉这种情况下的。 那怎么办？

  这个时候就需要手动加特判了。

  稍微想一下，只有在数字 $b > a$的情况下，$a - b$才可能为负。于是我们可以用非常玄学的运算式：

  $(a - b)= - (b - a)$

  如何实现这个操作？我们在判断 $b > a$ 成立后，可以调用函数$swap$交换$a，b$，然后再用一个判断$bool$型变量打上标记。

  交换过后，很明显，运算变为 $b - a$ ，而 $b > a$，显然运算不会出错。最后输出的时候，只需要在前面加一个负号即可。

  bool pd;
  if((a < b && a.size() == b.size()) || a.size() < b.size())
  {
  	 swap(a, b);//swap函数作用：交换两数
  	 pd = true;//打上标记
  }
  //----中间省略一堆计算代码-----
  
  if(pd == true)cout << "-";
  //b > a时，a - b < 0，打头输出负号
  
  //----后面省略一堆输出代码-----
  
  

  这里需要一提的是判断 $b > a$的方法。很显然，这里$a，b$都是字符串$string$型。为什么要这么写？

  这里涉及字典序的比较大小方式。$string$类型不是不能比大小，而是规则上有所不同

  粗略地概括一下：

  从最高位比起，$ASCII$码更大的字符串更大。如果相等，比次高位，以此向下类推。

  所以在$string$中，串 $9 > 89$ 。因为最高位$9 >8$

  当然，像前面几个数如果都相等，位数更大的显然更大。

  例如$1234500 > 12345$

  所以说：在位数相等的时候，我们可以直接利用字符串比大小的性质，来比较两数大小，但又要防止出现 $9 > 89$ 这种情况，所以还要保证位数大的数值才更大

  综上所述，得出这么一句判断。

  到此为止：我们得出来了高精度的$AC$代码

• 上代码！

#include<bits/stdc++.h>
#define mian main
#define QWQ puts("QWQ");
#define MAXN 10500 
//define是宏定义，define a b的作用是把a代替为b执行。 
//这里的意思是把MAXN替换成10500执行 
//请无视上方两个的宏定义（QWQ） 

using namespace std;

string a, b;
//选择字符串。因为字符串储存了每个串的长度，可以直接调用。
int na[MAXN], nb[MAXN], ans[MAXN]; 
bool pd;

int main()
{
    cin >> a >> b;
	if((a < b && a.size() == b.size()) || a.size() < b.size())
	{
		swap(a, b);
		pd = true;
	}
    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循环服务 
	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(pd == true)cout << "-";//b>a时，a - b < 0 所以打上负号 
	
	for(int i = maxl; i > 0; i --)cout << ans[i];
	if(maxl < 1)cout << "0";
    return 0;
}

• I Need More！！！

  这个代码的确可以$AC$整道题，但是并不是完美的高精度减法。

  • 当我们需要多次调用高精度运算时，这种写法就显得鸡肋了。

  • 并且，它并不能处理 $a$ 或 $b$ 为负数的情况。

  • 最重要的是，换种写法逼格更高

  但是这里就不写了，我挂在底下，有需求的可以自行了解哦（主要怕占版面太多 QWQ ）

  “就这么点东西根本无法满足我”

• 特别鸣谢：

  • 洛谷提供的平台

  • 管理员的辛勤审核

  • 大家的支持（没有大家的支持，我可能没有动力去更新Updata）

  希望大家能在评论区留言讨论，我会尽量看的！