高精度问题

在C或C++中, 整数高精度问题指的是数值计算范围超过long long的问题, 此时我们需要自己
实现数值的运算.

如果用大写字母表示高精度大整数(位数$len(A)\le 10^6$的整数), 用小写字母表示低精度小整数
(数值大小$a\le 10^9$可以用int存储), 则高高精度问题涉及:

• $A + B$
• $A - B$
• $A\times b$
• $A\;/\;b$

大整数的存储

1. 用数组存储整数的每一位.

2. 用数组下标低位存储数值低位, 与手写的顺序相反. 例如数字$123$在数组中存储顺序为$3, 2, 1$.
   这样做的好处是便于进位 — 让计算过程中多出的位在数组末尾扩展.

高精度运算的实现

$\;\;$
实现思路: 模拟手算.

$1.\;A + B$

• 实现思路: 计算结果的每一位的数值$ = A_i + B_i + t$, 即当前位以及上一位的进位的和.

• 注意: 因为数组的存储与手写或输入相反, 所以在将输入转为大存储存储和输出结果时需要逆序处理.

#include <vector>
#include <iostream>

using namespace std;

const int N = 1e6 + 10; //最高位数 不过对于变成数组vector可以不用

//C = A - B
vector<int> add(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    int t = 0; //进位
    for( int i = 0; i < A.size() || i < B.size(); i ++ )
    {
        if( i < A.size() )  t += A[i];
        if( i < B.size() )  t += B[i];
        C.push_back( t % 10 );
        t /= 10;
    }
    if( t ) C.push_back( t ); //仍有进位 这里t与1等价 因为t取值只有0或1
    return C;
}   

int main()
{
    string a, b;
    vector<int> A, B;

    cin >> a >> b;
    //因为大整数存储与手写相反 所以在输入和输出时需要逆序处理
    for( int i = a.size() - 1; i >= 0; i -- )   A.push_back( a[i] - '0' );
    for( int i = b.size() - 1; i >= 0; i -- )   B.push_back( b[i] - '0' );

    vector<int> C = add(A, B);
    for( int i = C.size() - 1; i >= 0; i -- )   cout << C[i];

    return 0;
}

$2.\;A - B$

• 思路: 对于结果, 其每一位$ = (A_i - B_i - t)\;\;[\;+\;10]$, $t$表示上一位的借位, 是否要$+ 10$取决于当前位
  是否需要借位.

• 为保证每次都可以借位, 我们需要保证$A\ge B$, 可以用一个比较函数实现.

• 需要考虑前导$0$的情况: 例如$123 - 123 = 000$, 我们需要去掉高位多余的$0$.

#include <vector>
#include <iostream>

using namespace std;

//判断A>=B
bool cmp(vector<int> &A, vector<int> &B)
{
    if( A.size() != B.size() )  return A.size() > B.size();
    for( int i = A.size() - 1; i >= 0; i -- ) //从高位到低位依次比较
        if( A[i] != B[i] )
            return A[i] > B[i];
    return true; //A == B
}

//C = A - B
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for( int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t; //t此时用于保存当前位的结果
        if( i < B.size() )  t -= B[i];
        C.push_back( (t + 10) % 10 );
        if( t < 0 ) t = 1; //此时t表示是否借位
        else    t = 0;
    }

    while( C.size() > 1 && C.back() == 0 )  C.pop_back(); //去掉前导0
    return C;
}

int main()
{
    string a, b;
    vector<int> A, B;

    cin >> a >> b;
    //因为大整数存储与手写相反 所以在输入和输出时需要逆序处理
    for( int i = a.size() - 1; i >= 0; i -- )   A.push_back( a[i] - '0' );
    for( int i = b.size() - 1; i >= 0; i -- )   B.push_back( b[i] - '0' );

    vector<int> C;
    if( cmp(A, B) )
    {
        C = sub(A, B);
    }
    else
    {
        C = sub(B, A);
        printf("-");
    }
    for( int i = C.size() - 1; i >= 0; i -- )   cout << C[i];

    return 0;
}

$3.\;A\times b$

• 思路: 每次用低精度整数$b$乘以高精度$A$的一位$A_i$, 那么当前位的计算结果为$s = A_i\times b + t$, 其中
  $t$为进位. 那么当前位的值$ = s \% 10$, 而下一位进位为$t = s / 10$.

• 注意: 此时的进位$t$不同意高进度加法的$t$ — 值为$0$/$1$. 这里的$t$可以是一个很大的数, 所以计算
  $A$的所有位后还需要判断进位$t$是否还有剩余; 同样的需要考虑前导$0$问题: 考虑$1234\times 0$的情况.

#include <vector>
#include <iostream>

using namespace std;

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;
    for( int i = 0, t = 0; i < A.size() || t; i ++ )
    {
        if( i < A.size() )  t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while( C.size() > 1 && C.back() == 0 )  C.pop_back();

    return C;
}

int main()
{
    string a;
    int b;
    vector<int> A;

    cin >> a >> b;
    for( int i = a.size() - 1; i >= 0; i -- )   A.push_back( a[i] - '0' );

    vector<int> C = mul(A, b);
    for( int i = C.size() - 1; i >= 0; i -- )   cout << C[i];

    return 0;
}

$4.\;A\;/\;b$

• 思路: 模拟手算过程 — 按照$A$数值位从高位到低位的顺序, 每次用当前数值$r\times 10 + A_i$与
  $b$运算, 其中$r$为上一位运算的余数. 则结果的当前位为$(r\times 10 + A_i) / b$, 当前位运算
  的余数为$(r\times 10 + A_i) \% b$.

• 注意: 这里计算的顺序与前几个运算相反, 是从高位到低位的. 所以计算的结果也是与之前的存储相反的.
  所以我们需要将结果逆序.(同一存储形式方便多种高精度运算同时进行). 另外注意前导$0$.

#include <vector>
#include <iostream>
#include <algorithm> //reverse()

using namespace std;

// C = A / b; r = A % b
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;

    for( int i = A.size() - 1; i >= 0; i -- ) //从高位到低位
    {
        r = r * 10 + A[i];
        C.push_back( r / b );
        r %= b;
    }

    reverse(C.begin(), C.end()); //逆序结果 统一存储格式
    while( C.size() > 1 && C.back() == 0 )  C.pop_back(); 

    return C;
}

int main()
{
    string a;
    int b, r;
    vector<int> A;

    cin >> a >> b;
    for( int i = a.size() - 1; i >= 0; i -- )   A.push_back( a[i] - '0' );

    vector<int> C = div(A, b, r);
    for( int i = C.size() - 1; i >= 0; i -- )   cout << C[i];
    cout << endl << r << endl;

    return 0;
}