前言

上一篇文章簡單提及了高精度加法運算，那么這次讓我們看看高精度乘法與高精度模板相應的實作吧！

一、高精度乘法

1.分析

回想一下A+B高精的實作，我們從豎式加法中得到啟發，發現了陣列實作大數加法的本質，那么這里我們不妨從豎式乘法的角度分析，通過下表來觀察其實質，

舉個例子，342*456=155,952，下表是每一位的運算程序，

仔細觀察可以發現，對于某兩位之間的乘法運算結果a[i]*b[j]，其對于最終結果的貢獻都在第i+j位上，利用這一條性質，我們可以先將所有的貢獻計算出來，最后進行進位處理，提升了運算效率，

2.例題

1.題面

傳送門: 洛谷P1303（A*B Problem）

2.AC代碼

附上AC代碼

#include<iostream>
#include<string>
using namespace std;
const int max_n = 2002;//最大位數
int a[max_n],b[max_n],c[max_n];
int main()
{
    string A,B;
    cin>>A>>B;
    int lenA = A.length(),lenB = B.length();
    for (int i = 0,j = lenA-1; j>=0; i++,j--)
        a[i] = A[j] - '0';
    for (int i = 0,j = lenB-1; j>=0; i++,j--)
        b[i] = B[j] - '0';
    for (int i = 0; i < lenA; i++){//計算每一位的貢獻
        for (int j = 0; j < lenB; j++){
            c[i+j] += a[i] * b[j];
        }
    }
    int len = lenA + lenB;//兩數乘積的最大位數不超過兩數位數之和
    for(int i = 0;i < len;i++){//從低位至高位依次處理進位
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    while (!c[len-1]){
        len--;//去除多余0位
    }
    for (int i = max(0,len-1);i >=0;i--)//這里使用max函式是為了處理乘數為0的情況
    {
        cout<<c[i];
    }//輸出
    return 0;
}

PS：此代碼的時間復雜度為O(n2)，n為數的位數，若要進行優化，則可以通過快速傅里葉變換來加速高精度乘法，將其優化為O(nlogn)，由于比較復雜，在此不作深入說明，

二、高精度模板

1.分析

到此，我們已經了解了用陣列模擬大數并進行加法與乘法的本質與方法，那么有一個很自然的問題，能不能使用一個模板，使得每次需要使用高精度運算時，或者同時需要使用加法與乘法運算時，能夠使用同一個模板進行運算呢？

根據C++的特性，我們可以通過封裝結構體，并多載運算子的方式來實作一個高精度模板，

2.實作

#define MAX_N 200
//封裝結構體
struct BigNum{
    int len;//數的位數
    int a[MAX_N];//各數位陣列

    BigNum(int x = 0){//通過初始化使其默認表示整形x = 0
        memset(a,0,sizeof(a));//初始化
        for (len = 0; x ;len++){
            a[len] = x % 10;
            x /= 10;
        }
    }
    int &operator [](int i){
        return a[i];
    }

    void flatten(int L){//從第0位到第L-1位進行進位處理，L不小于有效長度
        len = L;
        for(int i = 0;i < len;i++){//從低位至高位依次處理進位
        a[i + 1] += a[i] / 10;
        a[i] %= 10;
        }
        while (!a[len-1]){
            len--;//去除多余0位,使其重置為有效長度
        }
    }

    void print(){//輸出
        for (int i = max(0,len-1);i>=0;i--){
            printf("%d",a[i]);
        }
    }
};

//重置+(兩個大數相加)
BigNum operator+(BigNum a,BigNum b){
    BigNum c;
    int len = max(a.len,b.len);
    for (int i = 0; i<len ; i++ ){ //從低位至高位依次作加法運算
        c[i]+= a[i]+b[i];
    }
    c.flatten(len+1);
    return c;
}

//重置*(兩個大數相乘)
BigNum operator*(BigNum a,BigNum b){
    BigNum c;
    int lenA = a.len,lenB = b.len;
    for (int i = 0; i < lenA; i++){//計算每一位的貢獻
        for (int j = 0; j < lenB; j++){
            c[i+j] += a[i] * b[j];
        }
    }
    int max_len = lenA + lenB;
    c.flatten(max_len);
    return c;
}

//重置*(大數與int型相乘)
BigNum operator*(BigNum a,int b){
    BigNum c;
    int len = a.len;
    for (int i = 0; i < len; i++){//計算每一位的貢獻
            c[i] = a[i] * b;
    }
    c.flatten(len+11);//int型的最大長度為10位
    return c;
}

3.例題

例題傳送門：洛谷P1009（階乘之和）

1.題面

題目描述
用高精度計算出 S = 1 ! + 2 ! + 3 ! + ? + n ! （ n ≤ 50 ） S = 1! + 2! + 3! + \cdots + n!（n \le 50） S=1!+2!+3!+?+n!（n≤50）

輸入格式
一個正整數 n n n，

輸出格式
一個正整數 S S S，表示計算結果，

輸入輸出樣例
輸入 # 1 1 1
3 3 3
輸出 # 1 1 1
9 9 9

說明/提示
【資料范圍】
對于 100 % 100 \% 100% 的資料， 1 ≤ n ≤ 50 ， 1 \le n \le 50， 1≤n≤50，

2.分析

階乘達到22的時候，已經超出了long long的儲存范圍，這里利用前面寫封裝好的高精模板，就能輕松的解決此題，

3.AC代碼

添加上相應的頭檔案后，就能正常運行啦！（這里只貼出main函式模擬題意代碼）

int main(){
    BigNum ans(0),fac(1);
    int n;
    cin>>n;
    for (int i = 1;i <= n;i++){
        fac = fac * i;
        ans = ans + fac;
    }
    ans.print();
    return 0;
}

總結

到此為止，高精度運算就暫時告一段落了，高精度運算的主要實質為陣列模擬大數進行逐位運算，理解起來不算非常復雜，而通過進一步封裝，得到的高精度模板能夠方便簡潔地實作相應的大數運算，