高精度計(jì)算

有時(shí)候C語言內(nèi)置數(shù)據(jù)類型難以處理非常大的整數(shù)計(jì)算竣付，此時(shí)需要自己實(shí)現(xiàn)大整數(shù)計(jì)算缎患。

數(shù)字存儲方式

一般的高精度計(jì)算使用字符串作為輸入惋增，每個(gè)字符數(shù)字表示數(shù)字的一個(gè)十進(jìn)制位奸忽，平常的高精度計(jì)算實(shí)現(xiàn)類似我們平常在草稿紙上的計(jì)算方式，也就是豎式運(yùn)算清笨。

一般豎式運(yùn)算從個(gè)位開始計(jì)算月杉，所以為了計(jì)算方便抠艾，一般將大數(shù)從低位到高位存取。另外腌歉，數(shù)字的長度可能發(fā)生變化，但我們希望同樣權(quán)值位始終保持對齊（例如齐苛，希望所有的個(gè)位都在下標(biāo) [0] 凹蜂，所有的十位都在下標(biāo) [1] ……）馍驯，這都給了「反轉(zhuǎn)存儲」以充分的理由。

const int LEN = 1004;

//清空數(shù)字
void clear(short a[], int len) {
    for (int i = 0; i <= len; ++i) a[i] = 0;
}

void read(short a[]) {
    char s[LEN + 1];
    cin >> s;
    int len = strlen(s);
    clear(a, len);
    a[0] = len;//首位保存數(shù)字長度
    for (int i = 0; i < len; ++i) a[len - i] = s[i] - '0';//逆序存儲
}

輸出也按照存儲的逆序輸出汰瘫。因?yàn)橐话愀呶坏牧阋÷曰烀郑赃@里從最高位開始向下尋找第一個(gè)非零位蝗拿，從此處開始輸出哀托；終止條件 $i > 1$ 而不是 $i >= 1$ 是因?yàn)楫?dāng)整個(gè)數(shù)字等于 $0$ 時(shí)仍希望輸出一個(gè)字符 $0$ 仓手。

ostream &operator<<(ostream &os, const short a[]) {
    int i;
    for (i = a[0]; i > 1; --i)
        if (a[i] != 0) break;
    for (; i > 0; --i) cout << a[i];
    cout << '\n';
    return os;
}

嘗試打包一下這段代碼

#include<iostream>

using namespace std;
const int LEN = 1004;

class BigNum {
public:
    short a[LEN + 1];

    //清空數(shù)字
    void clear() {
        for (int i = 0; i <= LEN; ++i) a[i] = 0;
    }

    BigNum() {
        clear();
    }

    BigNum(const char *s) {
        int len = strlen(s);
        clear();
        a[0] = len;//首位保存數(shù)字長度
        for (int i = 0; i < len; ++i) a[len - i] = s[i] - '0';//逆序存儲
    }

    friend ostream &operator<<(ostream &os, const BigNum &num) {
        int i;
        for (i = num.a[0]; i > 1; --i)
            if (num.a[i] != 0) break;
        for (; i > 0; --i) cout << num.a[i];
        cout << '\n';
        return os;
    }

    friend istream &operator>>(istream &is, BigNum &num) {
        char s[LEN + 1];
        cin >> s;
        int len = strlen(s);
        num.clear();
        num.a[0] = len;//首位保存數(shù)字長度
        for (int i = 0; i < len; ++i) num.a[len - i] = s[i] - '0';//逆序存儲
        return is;
    }
};


int main() {
    BigNum a;
    cin >> a;
    cout << a;
    return 0;
}

1、大數(shù)加法

大數(shù)加法

從最低位開始辛慰，將兩個(gè)加數(shù)對應(yīng)位置上的數(shù)碼相加帅腌，并判斷是否達(dá)到或超過 $10$ 速客。如果達(dá)到溺职，那么處理進(jìn)位：將更高一位的結(jié)果上增加 $1$ 浪耘，當(dāng)前位的結(jié)果減少 $10$ 七冲。

    friend BigNum operator+(const BigNum &left, const BigNum &right) {
        BigNum c;
        // 高精度實(shí)現(xiàn)中澜躺，一般令數(shù)組的最大長度 LEN 比可能的輸入大一些
        // 然后略去末尾的幾次循環(huán)掘鄙，這樣一來可以省去不少邊界情況的處理
        // 因?yàn)閷?shí)際輸入不會超過 1000 位通铲，故在此循環(huán)到 LEN - 1 = 1003 已經(jīng)足夠
        int len = max(left.a[0], right.a[0]);
        for (int i = 1; i <= LEN; ++i) {
            // 將相應(yīng)位上的數(shù)碼相加
            c.a[i] += left.a[i] + right.a[i];
            if (c.a[i] >= 10) {
                // 進(jìn)位
                c.a[i + 1] += 1;
                c.a[i] -= 10;
            }
            if (i > len && c.a[i] != 0) len += 1;
        }
        c.a[0] = len;
        return c;
    }

2颅夺、大數(shù)減法

大數(shù)減法相比大數(shù)加法有些特殊吧黄，同樣是利用豎式運(yùn)算拗慨，我們平時(shí)做豎式減法的時(shí)候也可以發(fā)現(xiàn)赵抢，一般情況下烦却，都用大數(shù)減小數(shù)其爵，然后相應(yīng)的添加負(fù)號摩渺。

大數(shù)減法

簡潔起見摇幻，下面僅支持兩個(gè)正數(shù)相減丈咐，且必須是大數(shù)減小數(shù)

    friend BigNum operator-(const BigNum &left, const BigNum &right) {
        BigNum c;
        for (int i = 1; i <= LEN; ++i) {
            // 將相應(yīng)位上的數(shù)碼相加
            c.a[i] += a->a[i] - b->a[i];
            if (c.a[i] < 0) {
                // 進(jìn)位
                c.a[i + 1] -= 1;
                c.a[i] += 10;
            }
        }
        for (int i = 1; i <= a->a[0]; ++i) {
            if (c.a[i] != 0) c.a[0] = i;
        }
        return c;
    }

為了讓算法支持負(fù)數(shù)棵逊，應(yīng)該為 $BigNum$ 類添加符號標(biāo)志 $isNegative$ 辆影，指示當(dāng)前大數(shù)的正負(fù)號蛙讥；重新修正 $BigNum$ 中的加法和減法次慢，讓他們支持有符號運(yùn)算迫像。

#include<iostream>
#include<string>

using namespace std;
const int LEN = 1004;

class BigNum {
public:
    short a[LEN + 1];
    bool isNegative = false;

    //清空數(shù)字
    void clear() {
        for (int i = 0; i <= LEN; ++i) a[i] = 0;
    }

    BigNum() {
        clear();
    }

    BigNum(const char *s) {
        this->clear();
        int len = strlen(s);
        this->a[0] = len;
        int i = 0;
        this->isNegative = false;
        if (s[0] == '-') this->isNegative = true;
        if (s[0] == '-' || s[0] == '+') {
            i = 1;
            this->a[0] = len - 1;
        }
        for (; i < len; ++i) this->a[len - i] = s[i] - '0';
    }

    BigNum(const BigNum &num) {
        clear();
        this->isNegative = num.isNegative;
        for (int i = 0; i <= num.a[0]; ++i) this->a[i] = num.a[i];
    }

    BigNum &operator=(const BigNum &num) {
        if (this == &num) return *this;
        this->clear();
        this->isNegative = num.isNegative;
        for (int i = 0; i <= num.a[0]; ++i) this->a[i] = num.a[i];
        return *this;
    }

    BigNum &operator=(const char *s) {
        this->clear();
        int len = strlen(s);
        this->a[0] = len;
        int i = 0;
        this->isNegative = false;
        if (s[0] == '-') this->isNegative = true;
        if (s[0] == '-' || s[0] == '+') {
            i = 1;
            this->a[0] = len - 1;
        }
        for (; i < len; ++i) this->a[len - i] = s[i] - '0';
        return *this;
    }

    BigNum operator-() {
        BigNum new_num(*this);
        new_num.isNegative = !this->isNegative;
        return new_num;
    }

    BigNum operator+() {
        return BigNum(*this);
    }

    friend BigNum operator+(const BigNum &left, const BigNum &right) {
        BigNum c;
        //異號數(shù)字相加，也就是兩數(shù)字相減由缆，符號取決于絕對值大的數(shù)字
        if (left.isNegative != right.isNegative) {
            BigNum tmp = left;
            tmp.isNegative = right.isNegative;
            c = tmp - right;
            c.isNegative = left.a[0] > right.a[0] ? left.isNegative : right.isNegative;
            return c;
        }

        // 高精度實(shí)現(xiàn)中，一般令數(shù)組的最大長度 LEN 比可能的輸入大一些
        // 然后略去末尾的幾次循環(huán)舔箭，這樣一來可以省去不少邊界情況的處理
        // 因?yàn)閷?shí)際輸入不會超過 1000 位限嫌，故在此循環(huán)到 LEN - 1 = 1003 已經(jīng)足夠
        int len = max(left.a[0], right.a[0]);
        for (int i = 1; i <= LEN; ++i) {
            // 將相應(yīng)位上的數(shù)碼相加
            c.a[i] += left.a[i] + right.a[i];
            if (c.a[i] >= 10) {
                // 進(jìn)位
                c.a[i + 1] += 1;
                c.a[i] -= 10;
            }
            if (i > len && c.a[i] != 0) len += 1;
        }
        c.a[0] = len;
        c.isNegative = left.isNegative;
        return c;
    }

    friend BigNum operator-(const BigNum &left, const BigNum &right) {
        BigNum c;
        //異號數(shù)字相減怒医，相當(dāng)于無符號的兩個(gè)數(shù)相加稚叹，符號取決于被減數(shù)的符號
        if (left.isNegative != right.isNegative) {
            BigNum tmp = left;
            tmp.isNegative = right.isNegative;
            c = tmp + right;
            c.isNegative = left.isNegative;
            return c;
        }

        //同號數(shù)字相減扒袖，相當(dāng)于無符號大數(shù)減小數(shù)季率，符號取決于絕對值大的數(shù)在最終表達(dá)式中的符號
        const BigNum *a = &left;
        const BigNum *b = &right;
        c.isNegative = left.isNegative;
        if (left.a[0] < right.a[0]) {
            a = &right;
            b = &left;
            c.isNegative = !right.isNegative;
        }
        for (int i = 1; i <= LEN; ++i) {
            // 將相應(yīng)位上的數(shù)碼相減
            c.a[i] += a->a[i] - b->a[i];
            if (c.a[i] < 0) {
                // 進(jìn)位
                c.a[i + 1] -= 1;
                c.a[i] += 10;
            }
        }

        for (int i = a->a[0]; i > 1; --i) {
            if (c.a[i] != 0) {
                c.a[0] = i;
                break;
            }
        }
        return c;
    }

    friend ostream &operator<<(ostream &os, const BigNum &num) {
        int i;
        if (num.isNegative)
            cout << '-';
        for (i = num.a[0]; i > 1; --i)
            if (num.a[i] != 0) break;
        for (; i > 0; --i) cout << num.a[i];
        cout << '\n';
        return os;
    }

    friend istream &operator>>(istream &is, BigNum &num) {
        char s[LEN + 1];
        cin >> s;
        num = s;
        return is;
    }
};

3鞭光、高精度乘法--單精度

高精度乘法的單精度版本其實(shí)相當(dāng)于將 $a$ 的每一位數(shù)字乘以 $b$ 惰许，然后整合結(jié)果，如果 $b$ 過大晦毙，那么此算法就有可能出錯(cuò)（溢出）结序。
重整的方式，也是從個(gè)位開始逐位向上處理進(jìn)位邀层。但是這里的進(jìn)位可能非常大蜈出，甚至遠(yuǎn)大于 $9$ 凛澎，因?yàn)槊恳晃槐怀松现蠖伎赡苓_(dá)到 $9b$ 的數(shù)量級（如果確定 $9b$ 不會超過可用數(shù)值類型的范圍塑煎，可以使用這種方法）。所以這里的進(jìn)位不能再簡單地進(jìn)行 $-10$ 運(yùn)算冷尉，而是要通過除以 $10$ 的商以及余數(shù)計(jì)算雀哨。
例如: $a=1337震束，b=42$

高精度乘法--單精度

    //注意：前面將數(shù)組定義為short，這里為了增大單精度乘法的運(yùn)算范圍嘉栓，可以改為int侵佃、long long等馋辈。
    friend BigNum operator*(const BigNum &a, int b) {
        BigNum c;
        c.isNegative=a.isNegative != b<0;
        for (int i = 1; i <= LEN; ++i) {
            // 直接把 a 的第 i 位數(shù)碼乘以乘數(shù)迈螟，加入結(jié)果
            c.a[i] += a.a[i] * b;

            if (c.a[i] >= 10) {
                // 處理進(jìn)位
                // c[i] / 10 即除法的商數(shù)成為進(jìn)位的增量值
                c.a[i + 1] += c.a[i] / 10;
                // 而 c[i] % 10 即除法的余數(shù)成為在當(dāng)前位留下的值
                c.a[i] %= 10;
            }
        }
        for(int i=LEN;i>1;--i){
            if(c.a[i]!=0){
                c.a[0]=i;
                break;
            }
        }
        return c;
    }

4、高精度乘法--高精度

高精度乘法可以完全按照豎式乘法來計(jì)算洗搂。
回想豎式乘法的每一步耘拇，實(shí)際上是計(jì)算了若干 $a \times b_i \times 10^i$ 的和惫叛。例如計(jì)算 $1337 \times 42$ 挣棕，計(jì)算的就是 $1337 \times 2 \times 10^0 + 1337 \times 4 \times 10^1$ 洛心。

高精度乘法

    friend BigNum operator*(const BigNum &left, const BigNum &right) {
        BigNum c;
        //同號為正厅目、異號為負(fù)
        c.isNegative = left.isNegative != right.isNegative;
        for (int i = 1; i <= LEN; ++i) {
            // 這里直接計(jì)算結(jié)果中的從低到高第 i 位损敷，且一并處理了進(jìn)位
            // 第 i 次循環(huán)為 c[i] 加上了所有滿足 p + q = i 的 a[p] 與 b[q] 的乘積之和
            // 這樣做的效果和直接進(jìn)行上圖的運(yùn)算最后求和是一樣的拗馒，只是更加簡短的一種實(shí)現(xiàn)方式
            for (int j = 1; j <= i; ++j)
                c.a[i] += left.a[j] * right.a[i - j + 1];

            if (c.a[i] >= 10) {
                c.a[i + 1] += c.a[i] / 10;
                c.a[i] %= 10;
            }
        }
        for (int i = LEN; i > 1; --i) {
            if (c.a[i] != 0) {
                c.a[0] = i;
                break;
            }
        }
        return c;
    }

5、高精度除法

高精度除法

豎式長除法實(shí)際上可以看作一個(gè)逐次減法的過程挥等。例如上圖中商數(shù)十位的計(jì)算可以這樣理解：將 $45$ 減去三次 $12$ 后變得小于 $12$ ，不能再減辞槐，故此位為 $3$ 催蝗。

為了減少冗余運(yùn)算，我們提前得到被除數(shù)的長度 $l_a$ 與除數(shù)的長度 $l_b$ 缰冤，從下標(biāo) $l_a-l_b$ 開始棉浸，從高位到低位來計(jì)算商枝恋。這和手工計(jì)算時(shí)將第一次乘法的最高位與被除數(shù)最高位對齊的做法是一樣的焚碌。

參考程序?qū)崿F(xiàn)了一個(gè)函數(shù) greater_eq() 用于判斷被除數(shù)以下標(biāo) last_dg 為最低位十电，是否可以再減去除數(shù)而保持非負(fù)鹃骂。此后對于商的每一位畏线，不斷調(diào)用 greater_eq() ，并在成立的時(shí)候用高精度減法從余數(shù)中減去除數(shù)杯矩，也即模擬了豎式除法的過程

    // 被除數(shù) a 以下標(biāo) last_dg 為最低位史隆，是否可以再減去除數(shù) b 而保持非負(fù)
    // len 是除數(shù) b 的長度泌射，避免反復(fù)計(jì)算
    static bool greater_eq(const BigNum &a, const BigNum &b, int last_dg, int lb) {
        // 有可能被除數(shù)剩余的部分比除數(shù)長，這個(gè)情況下最多多出 1 位拒秘，故如此判斷即可
        if (a.a[last_dg + lb + 1] != 0) return true;
        // 從高位到低位躺酒，逐位比較
        for (int i = lb; i >= 1; --i) {
            if (a.a[last_dg + i] > b.a[i]) return true;
            if (a.a[last_dg + i] < b.a[i]) return false;
        }
        // 相等的情形下也是可行的
        return true;
    }

    friend BigNum operator/(const BigNum &left, const BigNum &right) {
        BigNum c;
        c.isNegative = left.isNegative != right.isNegative;

        int la = left.a[0], lb = right.a[0];

        if (lb == 0) {
            cout << "> <";
            return c;
        }  // 除數(shù)不能為零

        // c 是商
        // d 是被除數(shù)的剩余部分羹应，算法結(jié)束后自然成為余數(shù)
        BigNum d = left;
        for (int i = la - lb; i >= 0; --i) {
            // 計(jì)算商的第 i 位
            while (BigNum::greater_eq(d, right, i, lb)) {
                // 若可以減雳刺，則減
                // 這一段是一個(gè)高精度減法
                for (int j = 1; j <= lb; ++j) {
                    d.a[i + j] -= right.a[j];
                    if (d.a[i + j] < 0) {
                        d.a[i + j + 1] -= 1;
                        d.a[i + j] += 10;
                    }
                }
                // 使商的這一位增加 1
                c.a[i + 1] += 1;
                // 返回循環(huán)開頭掖桦，重新檢查
            }
        }
        c.a[0] = 1;
        for (int i = LEN; i > 1; --i) {
            if (c.a[i] != 0) {
                c.a[0] = i;
                break;
            }
        }
        return c;
    }

無符號簡潔模版

class UBigNum {
public:
    int a[LEN + 1];

    //清空數(shù)字
    void clear() {
        for (int i = 0; i <= LEN; ++i) a[i] = 0;
    }

    UBigNum() {
        clear();
    }

    UBigNum(const char *s) {
        this->clear();
        int len = strlen(s);
        this->a[0] = len;
        int i = 0;
        for (; i < len; ++i) this->a[len - i] = s[i] - '0';
    }

    UBigNum(const UBigNum &num) {
        clear();
        for (int i = 0; i <= num.a[0]; ++i) this->a[i] = num.a[i];
    }

    UBigNum &operator=(const UBigNum &num) {
        if (this == &num) return *this;
        this->clear();
        for (int i = 0; i <= num.a[0]; ++i) this->a[i] = num.a[i];
        return *this;
    }

    UBigNum &operator=(const char *s) {
        this->clear();
        int len = strlen(s);
        this->a[0] = len;
        int i = 0;
        for (; i < len; ++i) this->a[len - i] = s[i] - '0';
        return *this;
    }

    static int computeLens(const UBigNum &num){
        int lens = 1;
        for (int i = LEN; i > 1; --i) {
            if (num.a[i] != 0) {
                lens=i;
                break;
            }
        }
        return lens;
    }

    friend UBigNum operator+(const UBigNum &left, const UBigNum &right) {
        UBigNum c;
        // 高精度實(shí)現(xiàn)中紊馏，一般令數(shù)組的最大長度 LEN 比可能的輸入大一些
        // 然后略去末尾的幾次循環(huán)朱监，這樣一來可以省去不少邊界情況的處理
        // 因?yàn)閷?shí)際輸入不會超過 1000 位赫编，故在此循環(huán)到 LEN - 1 = 1003 已經(jīng)足夠
        int len = max(left.a[0], right.a[0]);
        for (int i = 1; i <= LEN; ++i) {
            // 將相應(yīng)位上的數(shù)碼相加
            c.a[i] += left.a[i] + right.a[i];
            if (c.a[i] >= 10) {
                // 進(jìn)位
                c.a[i + 1] += 1;
                c.a[i] -= 10;
            }
        }
        c.a[0] = c.a[len + 1] == 0 ? len : len + 1;
        return c;
    }

    //只返回大數(shù)減小數(shù)的結(jié)果悦荒，符號需要自己判斷
    friend UBigNum operator-(const UBigNum &left, const UBigNum &right) {
        UBigNum c;

        //同號數(shù)字相減搬味，相當(dāng)于無符號大數(shù)減小數(shù)碰纬，符號取決于絕對值大的數(shù)在最終表達(dá)式中的符號
        const UBigNum *a = &left;
        const UBigNum *b = &right;
        if (left.a[0] < right.a[0]) {
            a = &right;
            b = &left;
        }
        for (int i = 1; i <= LEN; ++i) {
            // 將相應(yīng)位上的數(shù)碼相減
            c.a[i] += a->a[i] - b->a[i];
            if (c.a[i] < 0) {
                // 進(jìn)位
                c.a[i + 1] -= 1;
                c.a[i] += 10;
            }
        }
        c.a[0] = UBigNum::computeLens(c);
        return c;
    }

    friend UBigNum operator*(const UBigNum &a, int b) {
        UBigNum c;
        for (int i = 1; i <= LEN; ++i) {
            // 直接把 a 的第 i 位數(shù)碼乘以乘數(shù)，加入結(jié)果
            c.a[i] += a.a[i] * b;

            if (c.a[i] >= 10) {
                // 處理進(jìn)位
                // c[i] / 10 即除法的商數(shù)成為進(jìn)位的增量值
                c.a[i + 1] += c.a[i] / 10;
                // 而 c[i] % 10 即除法的余數(shù)成為在當(dāng)前位留下的值
                c.a[i] %= 10;
            }
        }
        c.a[0] = UBigNum::computeLens(c);
        return c;
    }

    friend UBigNum operator*(const UBigNum &left, const UBigNum &right) {
        UBigNum c;
        for (int i = 1; i <= LEN; ++i) {
            // 這里直接計(jì)算結(jié)果中的從低到高第 i 位强戴，且一并處理了進(jìn)位
            // 第 i 次循環(huán)為 c[i] 加上了所有滿足 p + q = i 的 a[p] 與 b[q] 的乘積之和
            // 這樣做的效果和直接進(jìn)行上圖的運(yùn)算最后求和是一樣的媒佣，只是更加簡短的一種實(shí)現(xiàn)方式
            for (int j = 1; j <= i; ++j)
                c.a[i] += left.a[j] * right.a[i - j + 1];

            if (c.a[i] >= 10) {
                c.a[i + 1] += c.a[i] / 10;
                c.a[i] %= 10;
            }
        }
        c.a[0] = UBigNum::computeLens(c);
        return c;
    }

    // 被除數(shù) a 以下標(biāo) last_dg 為最低位，是否可以再減去除數(shù) b 而保持非負(fù)
    // len 是除數(shù) b 的長度衰琐，避免反復(fù)計(jì)算
    static bool greater_eq(const UBigNum &a, const UBigNum &b, int last_dg, int lb) {
        // 有可能被除數(shù)剩余的部分比除數(shù)長，這個(gè)情況下最多多出 1 位狗热，故如此判斷即可
        if (a.a[last_dg + lb + 1] != 0) return true;
        // 從高位到低位匿刮，逐位比較
        for (int i = lb; i >= 1; --i) {
            if (a.a[last_dg + i] > b.a[i]) return true;
            if (a.a[last_dg + i] < b.a[i]) return false;
        }
        // 相等的情形下也是可行的
        return true;
    }

    friend UBigNum operator/(const UBigNum &left, const UBigNum &right) {
        UBigNum c;
        int la = left.a[0], lb = right.a[0];

        if (lb == 0) {
            cout << "> <";
            return c;
        }  // 除數(shù)不能為零

        // c 是商
        // d 是被除數(shù)的剩余部分，算法結(jié)束后自然成為余數(shù)
        UBigNum d = left;
        for (int i = la - lb; i >= 0; --i) {
            // 計(jì)算商的第 i 位
            while (UBigNum::greater_eq(d, right, i, lb)) {
                // 若可以減光羞，則減
                // 這一段是一個(gè)高精度減法
                for (int j = 1; j <= lb; ++j) {
                    d.a[i + j] -= right.a[j];
                    if (d.a[i + j] < 0) {
                        d.a[i + j + 1] -= 1;
                        d.a[i + j] += 10;
                    }
                }
                // 使商的這一位增加 1
                c.a[i + 1] += 1;
                // 返回循環(huán)開頭，重新檢查
            }
        }
        c.a[0] = UBigNum::computeLens(c);
        return c;
    }


    friend ostream &operator<<(ostream &os, const UBigNum &num) {
        int i;
        for (i = num.a[0]; i > 1; --i)
            if (num.a[i] != 0) break;
        for (; i > 0; --i) cout << num.a[i];
        cout << '\n';
        return os;
    }

    friend istream &operator>>(istream &is, UBigNum &num) {
        char s[LEN + 1];
        cin >> s;
        num = s;
        return is;
    }
};

優(yōu)化

實(shí)際上前面所述的方案數(shù)組中的每個(gè)數(shù)字表示的是大數(shù)中的某一位數(shù)潜慎，此方案實(shí)際上對int數(shù)組的利用效率比較低，能不能使得數(shù)組中的每個(gè)數(shù)字表示連續(xù)的 $t$ 位有效數(shù)字呢驳遵？

網(wǎng)友實(shí)現(xiàn)的版本

#include<algorithm>
#include<unordered_map>

using namespace std;
const int power = 4; //壓位
const int base = 10000;
const int MAXL = 106;

struct num //高精度模板堤结，很好理解的
{
    int a[MAXL];

    num() { memset(a, 0, sizeof a); }

    num(const char *s, int len) {
        memset(a, 0, sizeof(a));
        a[0] = (len + power - 1) / power;//a[0]保存數(shù)字長度唐责，此時(shí)一個(gè)int保存一個(gè)4位長度的數(shù)字
        for (int i = 0, t = 0, w; i < len; w *= 10, ++i) {
            if (i % power == 0) { w = 1, ++t; }
            a[t] += w * (s[i] - '0');
        }
    }

    void add(int k) { if (k || a[0]) a[++a[0]] = k; }

    void re() { reverse(a + 1, a + a[0] + 1); }          //STL自帶的反轉(zhuǎn)字符串的函數(shù)
    void print() {
        printf("%d", a[a[0]]);
        for (int i = a[0] - 1; i > 0; --i)
            printf("%0*d", power, a[i]);
        printf("\n");
    }

};

bool operator<(const num &p, const num &q) {
    if (p.a[0] < q.a[0]) return true;
    if (p.a[0] > q.a[0]) return false;
    for (int i = p.a[0]; i > 0; --i) {
        if (p.a[i] != q.a[i]) return p.a[i] < q.a[i];
    }
    return false;
}

num operator*(const num &p, const num &q) {
    num c;
    c.a[0] = p.a[0] + q.a[0] - 1;
    for (int i = 1; i <= p.a[0]; ++i)
        for (int j = 1; j <= q.a[0]; ++j) {
            c.a[i + j - 1] += p.a[i] * q.a[j];
            c.a[i + j] += c.a[i + j - 1] / base;
            c.a[i + j - 1] %= base;
        }
    if (c.a[c.a[0] + 1]) ++c.a[0];
    return c;
}

根據(jù)網(wǎng)友版本更改而來

const int power = 4, base = 10000;//base=10^4
class UNum {
public:
    int a[LEN + 1];

    //清空數(shù)字
    void clear() {
        for (int i = 0; i <= LEN; ++i) a[i] = 0;
    }

    UNum() {
        clear();
    }

    UNum(const char *s) {
        this->clear();
        int len = strlen(s);
        //a[0]保存數(shù)字長度，此時(shí)一個(gè)int保存一個(gè)4位長度的數(shù)字
        a[0] = (len + power - 1) / power;
        for (int t = 1; t <= a[0]; ++t) {
            for (int i = max(len - t * power, 0); i < min(len, len - t * power + power); ++i) {
                a[t] = 10 * a[t] + (s[i] - '0');
            }
        }
    }

    UNum(const UNum &num) {
        clear();
        for (int i = 0; i <= num.a[0]; ++i) this->a[i] = num.a[i];
    }

    UNum &operator=(const UNum &num) {
        if (this == &num) return *this;
        this->clear();
        for (int i = 0; i <= num.a[0]; ++i) this->a[i] = num.a[i];
        return *this;
    }

    UNum &operator=(const char *s) {
        this->clear();
        int len = strlen(s);
        //a[0]保存數(shù)字長度，此時(shí)一個(gè)int保存一個(gè)4位長度的數(shù)字
        a[0] = (len + power - 1) / power;
        for (int t = 1; t <= a[0]; ++t) {
            for (int i = max(len - t * power, 0); i < min(len, len - t * power + power); ++i) {
                a[t] = 10 * a[t] + (s[i] - '0');
            }
        }
        return *this;
    }

    static int computeLens(const UNum &num) {
        int lens = 1;
        for (int i = LEN; i > 1; --i) {
            if (num.a[i] != 0) {
                lens = i;
                break;
            }
        }
        return lens;
    }

    //STL自帶的反轉(zhuǎn)字符串的函數(shù)
    void re() { reverse(a + 1, a + a[0] + 1); }

    friend UNum operator+(const UNum &left, const UNum &right) {
        UNum c;
        int len = max(left.a[0], right.a[0]);
        for (int i = 1; i <= LEN; ++i) {
            // 將相應(yīng)位上的數(shù)碼相加
            c.a[i] += left.a[i] + right.a[i];
            if (c.a[i] >= base) {
                // 進(jìn)位
                c.a[i + 1] += 1;
                c.a[i] -= base;
            }
        }
        c.a[0] = c.a[len + 1] == 0 ? len : len + 1;
        return c;
    }

    //只返回大數(shù)減小數(shù)的結(jié)果，符號需要自己判斷
    friend UNum operator-(const UNum &left, const UNum &right) {
        UNum c;
        const UNum *a = &left;
        const UNum *b = &right;
        if (left.a[0] < right.a[0]) {
            a = &right;
            b = &left;
        }
        for (int i = 1; i <= LEN; ++i) {
            // 將相應(yīng)位上的數(shù)碼相減
            c.a[i] += a->a[i] - b->a[i];
            if (c.a[i] < 0) {
                // 進(jìn)位
                c.a[i + 1] -= 1;
                c.a[i] += base;
            }
        }
        c.a[0] = UNum::computeLens(c);
        return c;
    }

    friend bool operator<(const UNum &p, const UNum &q) {
        if (p.a[0] < q.a[0]) return true;
        if (p.a[0] > q.a[0]) return false;
        for (int i = p.a[0]; i > 0; --i) {
            if (p.a[i] != q.a[i]) return p.a[i] < q.a[i];
        }
        return false;
    }

    friend UNum operator*(const UNum &p, const UNum &q) {
        UNum c;
        c.a[0] = p.a[0] + q.a[0] - 1;
        for (int i = 1; i <= p.a[0]; ++i)
            for (int j = 1; j <= q.a[0]; ++j) {
                c.a[i + j - 1] += p.a[i] * q.a[j];
                c.a[i + j] += c.a[i + j - 1] / base;
                c.a[i + j - 1] %= base;
            }
        if (c.a[c.a[0] + 1]) ++c.a[0];
        return c;
    }

    friend ostream &operator<<(ostream &os, const UNum &num) {
        int i = num.a[0];
        cout << num.a[i--];
        for (; i > 0; --i) cout << setw(power) << setfill('0') << num.a[i];
        cout << '\n';
        return os;
    }

    friend istream &operator>>(istream &is, UNum &num) {
        char s[LEN + 1];
        cin >> s;
        num = s;
        return is;
    }
};

另外高精度乘法還有更優(yōu)的Karatsuba算法，時(shí)間復(fù)雜度更低

Karatsuba 乘法

記高精度數(shù)字的位數(shù)為 $n$ ，那么高精度—高精度豎式乘法需要花費(fèi) $O(n^2)$ 的時(shí)間乳怎。本節(jié)介紹一個(gè)時(shí)間復(fù)雜度更為優(yōu)秀的算法蚪缀，由前蘇聯(lián)（俄羅斯）數(shù)學(xué)家 Anatoly Karatsuba 提出，是一種分治算法金蜀。

考慮兩個(gè)十進(jìn)制大整數(shù) $x$ 和 $y$ 渊抄，均包含 $n$ 個(gè)數(shù)碼（可以有前導(dǎo)零）。任取 $0 < m < n$ 丧裁，記

$\begin{aligned} x &= x_1 \cdot 10^m + x_0, \\ y &= y_1 \cdot 10^m + y_0, \\ x \cdot y &= z_2 \cdot 10^{2m} + z_1 \cdot 10^m + z_0, \end{aligned}$

其中 $x_0, y_0, z_0, z_1 < 10^m$ 护桦。可得

$\begin{aligned} z_2 &= x_1 \cdot y_1, \\ z_1 &= x_1 \cdot y_0 + x_0 \cdot y_1, \\ z_0 &= x_0 \cdot y_0. \end{aligned}$

觀察知

$z_1 = (x_1 + x_0) \cdot (y_1 + y_0) - z_2 - z_0,$

于是要計(jì)算 $z_1$ 煎娇，只需計(jì)算 $(x_1 + x_0) \cdot (y_1 + y_0)$ 二庵，再與 $z_0$ 贪染、 $z_2$ 相減即可催享。

上式實(shí)際上是 Karatsuba 算法的核心杭隙，它將長度為 $n$ 的乘法問題轉(zhuǎn)化為了 $3$ 個(gè)長度更小的子問題。若令 $m = \left\lceil \frac n 2 \right\rceil$ 因妙，記 Karatsuba 算法計(jì)算兩個(gè) $n$ 位整數(shù)乘法的耗時(shí)為 $T(n)$ 痰憎，則有 $T(n) = 3 \cdot T \left(\left\lceil \frac n 2 \right\rceil\right) + O(n)$ ，由主定理可得 $T(n) = \Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})$ 兰迫。

整個(gè)過程可以遞歸實(shí)現(xiàn)信殊。為清晰起見炬称，下面的代碼通過 Karatsuba 算法實(shí)現(xiàn)了多項(xiàng)式乘法汁果，最后再處理所有的進(jìn)位問題。

??? "karatsuba_mulc.cpp"

int *karatsuba_polymul(int n, int *a, int *b) {
  if (n <= 32) {
    // 規(guī)模較小時(shí)直接計(jì)算玲躯，避免繼續(xù)遞歸帶來的效率損失
    int *r = new int[n * 2 + 1]();
    for (int i = 0; i <= n; ++i)
      for (int j = 0; j <= n; ++j) r[i + j] += a[i] * b[j];
    return r;
  }
    
  int m = n / 2 + 1;
  int *r = new int[m * 4 + 1]();
  int *z0, *z1, *z2;
    
  z0 = karatsuba_polymul(m - 1, a, b);
  z2 = karatsuba_polymul(n - m, a + m, b + m);
    
  // 計(jì)算 z1
  // 臨時(shí)更改据德，計(jì)算完畢后恢復(fù)
  for (int i = 0; i + m <= n; ++i) a[i] += a[i + m];
  for (int i = 0; i + m <= n; ++i) b[i] += b[i + m];
  z1 = karatsuba_polymul(m - 1, a, b);
  for (int i = 0; i + m <= n; ++i) a[i] -= a[i + m];
  for (int i = 0; i + m <= n; ++i) b[i] -= b[i + m];
  for (int i = 0; i <= (m - 1) * 2; ++i) z1[i] -= z0[i];
  for (int i = 0; i <= (n - m) * 2; ++i) z1[i] -= z2[i];
    
  // 由 z0、z1跷车、z2 組合獲得結(jié)果
  for (int i = 0; i <= (m - 1) * 2; ++i) r[i] += z0[i];
  for (int i = 0; i <= (m - 1) * 2; ++i) r[i + m] += z1[i];
  for (int i = 0; i <= (n - m) * 2; ++i) r[i + m * 2] += z2[i];
    
  delete[] z0;
  delete[] z1;
  delete[] z2;
  return r;
}
    
void karatsuba_mul(int a[], int b[], int c[]) {
  int *r = karatsuba_polymul(LEN - 1, a, b);
  memcpy(c, r, sizeof(int) * LEN);
  for (int i = 0; i < LEN - 1; ++i)
    if (c[i] >= 10) {
      c[i + 1] += c[i] / 10;
      c[i] %= 10;
    }
  delete[] r;
}

但是這樣的實(shí)現(xiàn)存在一個(gè)問題：在 $b$ 進(jìn)制下棘利，多項(xiàng)式的每一個(gè)系數(shù)都有可能達(dá)到 $n \cdot b^2$ 量級，在壓位高精度實(shí)現(xiàn)（即 $b > 10$ 朽缴，下文介紹）中可能造成整數(shù)溢出善玫；而若在多項(xiàng)式乘法的過程中處理進(jìn)位問題，則 $x_1 + x_0$ 與 $y_1 + y_0$ 的結(jié)果可能達(dá)到 $2 \cdot b^m$ 密强，增加一個(gè)位（如果采用 $x_1 - x_0$ 的計(jì)算方式茅郎，則不得不特殊處理負(fù)數(shù)的情況）。因此或渤，需要依照實(shí)際的應(yīng)用場景來決定采用何種實(shí)現(xiàn)方式系冗。

Reference

https://en.wikipedia.org/wiki/Karatsuba_algorithm
https://oi-wiki.org/math/bignum/

封裝類

這里有一個(gè)封裝好的高精度整數(shù)類。

#define MAXN 9999
// MAXN 是一位中最大的數(shù)字
#define MAXSIZE 10024
// MAXSIZE 是位數(shù)
#define DLEN 4
// DLEN 記錄壓幾位
struct Big {
  int a[MAXSIZE], len;
  bool flag;  //標(biāo)記符號'-'
  Big() {
    len = 1;
    memset(a, 0, sizeof a);
    flag = 0;
  }
  Big(const int);
  Big(const char*);
  Big(const Big&);
  Big& operator=(const Big&);  //注意這里operator有&薪鹦，因?yàn)橘x值有修改……
  //由于OI中要求效率
  //此處不使用泛型函數(shù)
  //故不重載
  // istream& operator>>(istream&,  BigNum&);   //重載輸入運(yùn)算符
  // ostream& operator<<(ostream&,  BigNum&);   //重載輸出運(yùn)算符
  Big operator+(const Big&) const;
  Big operator-(const Big&) const;
  Big operator*(const Big&)const;
  Big operator/(const int&) const;
  // TODO: Big / Big;
  Big operator^(const int&) const;
  // TODO: Big ^ Big;
    
  // TODO: Big 位運(yùn)算;
    
  int operator%(const int&) const;
  // TODO: Big ^ Big;
  bool operator<(const Big&) const;
  bool operator<(const int& t) const;
  inline void print();
};
// README::不要隨隨便便把參數(shù)都變成引用掌敬，那樣沒辦法傳值
Big::Big(const int b) {
  int c, d = b;
  len = 0;
  // memset(a,0,sizeof a);
  CLR(a);
  while (d > MAXN) {
    c = d - (d / (MAXN + 1) * (MAXN + 1));
    d = d / (MAXN + 1);
    a[len++] = c;
  }
  a[len++] = d;
}
Big::Big(const char* s) {
  int t, k, index, l;
  CLR(a);
  l = strlen(s);
  len = l / DLEN;
  if (l % DLEN) ++len;
  index = 0;
  for (int i = l - 1; i >= 0; i -= DLEN) {
    t = 0;
    k = i - DLEN + 1;
    if (k < 0) k = 0;
    g(j, k, i) t = t * 10 + s[j] - '0';
    a[index++] = t;
  }
}
Big::Big(const Big& T) : len(T.len) {
  CLR(a);
  f(i, 0, len) a[i] = T.a[i];
  // TODO:重載此處？
}
Big& Big::operator=(const Big& T) {
  CLR(a);
  len = T.len;
  f(i, 0, len) a[i] = T.a[i];
  return *this;
}
Big Big::operator+(const Big& T) const {
  Big t(*this);
  int big = len;
  if (T.len > len) big = T.len;
  f(i, 0, big) {
    t.a[i] += T.a[i];
    if (t.a[i] > MAXN) {
      ++t.a[i + 1];
      t.a[i] -= MAXN + 1;
    }
  }
  if (t.a[big])
    t.len = big + 1;
  else
    t.len = big;
  return t;
}
Big Big::operator-(const Big& T) const {
  int big;
  bool ctf;
  Big t1, t2;
  if (*this < T) {
    t1 = T;
    t2 = *this;
    ctf = 1;
  } else {
    t1 = *this;
    t2 = T;
    ctf = 0;
  }
  big = t1.len;
  int j = 0;
  f(i, 0, big) {
    if (t1.a[i] < t2.a[i]) {
      j = i + 1;
      while (t1.a[j] == 0) ++j;
      --t1.a[j--];
      // WTF?
      while (j > i) t1.a[j--] += MAXN;
      t1.a[i] += MAXN + 1 - t2.a[i];
    } else
      t1.a[i] -= t2.a[i];
  }
  t1.len = big;
  while (t1.len > 1 && t1.a[t1.len - 1] == 0) {
    --t1.len;
    --big;
  }
  if (ctf) t1.a[big - 1] = -t1.a[big - 1];
  return t1;
}
Big Big::operator*(const Big& T) const {
  Big res;
  int up;
  int te, tee;
  f(i, 0, len) {
    up = 0;
    f(j, 0, T.len) {
      te = a[i] * T.a[j] + res.a[i + j] + up;
      if (te > MAXN) {
        tee = te - te / (MAXN + 1) * (MAXN + 1);
        up = te / (MAXN + 1);
        res.a[i + j] = tee;
      } else {
        up = 0;
        res.a[i + j] = te;
      }
    }
    if (up) res.a[i + T.len] = up;
  }
  res.len = len + T.len;
  while (res.len > 1 && res.a[res.len - 1] == 0) --res.len;
  return res;
}
Big Big::operator/(const int& b) const {
  Big res;
  int down = 0;
  gd(i, len - 1, 0) {
    res.a[i] = (a[i] + down * (MAXN + 1) / b);
    down = a[i] + down * (MAXN + 1) - res.a[i] * b;
  }
  res.len = len;
  while (res.len > 1 && res.a[res.len - 1] == 0) --res.len;
  return res;
}
int Big::operator%(const int& b) const {
  int d = 0;
  gd(i, len - 1, 0) d = (d * (MAXN + 1) % b + a[i]) % b;
  return d;
}
Big Big::operator^(const int& n) const {
  Big t(n), res(1);
  // TODO::快速冪這樣寫好丑= =//DONE:)
  int y = n;
  while (y) {
    if (y & 1) res = res * t;
    t = t * t;
    y >>= 1;
  }
  return res;
}
bool Big::operator<(const Big& T) const {
  int ln;
  if (len < T.len) return 233;
  if (len == T.len) {
    ln = len - 1;
    while (ln >= 0 && a[ln] == T.a[ln]) --ln;
    if (ln >= 0 && a[ln] < T.a[ln]) return 233;
    return 0;
  }
  return 0;
}
inline bool Big::operator<(const int& t) const {
  Big tee(t);
  return *this < tee;
}
inline void Big::print() {
  printf("%d", a[len - 1]);
  gd(i, len - 2, 0) { printf("%04d", a[i]); }
}
    
inline void print(Big s) {
  // s不要是引用池磁，要不然你怎么print(a * b);
  int len = s.len;
  printf("%d", s.a[len - 1]);
  gd(i, len - 2, 0) { printf("%04d", s.a[i]); }
}
char s[100024];