A2 高精度减法 • EH's Blog

题目情境#

题目链接：https://www.luogu.com.cn/problem/P2142 ↗

题目描述

高精度减法。

输入格式

两个整数 a,b（第二个可能比第一个大）。

输出格式

结果（是负数要输出负号）。

输入输出样例

输入 #1

2
1

plaintext

输出 #1

plaintext

算法解析#

高精度计算实际上用数组存储和模拟运算。高精度减法的步骤：

高精度数字利用字符串读入；

把字符串翻转存入两个整型数组 A,B；

若 A<B，则交换 A,B，输出负号；

从低位到高位，逐位求差，借位，存差；

把数组 C 从高位到低位依次输出。

时间复杂度O(n)

Python代码实现#

a = int(input())
b = int(input())
print(a - b)

python

C++代码实现#

#include <iostream>
using namespace std;

const int N=20000;
int a[N],b[N],c[N];
int la,lb,lc;

bool cmp(int a[],int b[]){
    if(la!=lb) return la<lb;
    for(int i=la; i; i--)
        if(a[i]!=b[i]) return a[i]<b[i];
    return false;  //相等时,避免-0
}
void sub(int a[],int b[],int c[]){ //a-b=c
    for(int i=1; i<=lc; i++){
        if(a[i]<b[i]) a[i+1]--,a[i]+=10;
        c[i]=a[i]-b[i];
    }
    while(c[lc]==0&&lc>1) lc--; //去0
}
int main(){
    string sa,sb; cin>>sa>>sb;
    la=sa.size(),lb=sb.size(),lc=max(la,lb);
    for(int i=1;i<=la;i++) a[i]=sa[la-i]-'0';
    for(int i=1;i<=lb;i++) b[i]=sb[lb-i]-'0';
    if(cmp(a,b)) swap(a,b),cout<<'-';
    sub(a,b,c);
    for(int i=lc;i;i--) printf("%d",c[i]);
    return 0;
}