高精度

注意该模板只能处理正数的+-*/%，如果正数-正数为负数，也可以处理，但不能处理负数的运算，如-1+3

若要处理负数，则需要先转化为正数

另外，此模板不能处理高精/高精和高精%单精

struct bign
{
    int len, s[N];//s[N]里从0~n-1倒序存储大整数，例如12345存储为s[]={5,4,3,2,1},此时len为5
    bign() { memset(s, 0, sizeof(s));  len = 1; }
    bign(int num) { *this = num; }
    bign(char* num) { *this = num; }
    bign operator =(int num)
    {
        char c[N];
        sprintf(c, "%d", num);
        *this = c;
        return *this;
    }
    bign operator =(const char* num)
    {
        len = strlen(num);
        for (int i = 0; i < len; i++) s[i] = num[len - 1 - i] - '0';
        return *this;
    }
    string str()//转化为string,以便输出
    {
        string res = "";
        if (s[len - 1] < 0) res += '-';
        for (int i = len - 1; i >= 0; i--) {
            if (s[i] < 0) s[i] = -s[i];
            res += s[i] + '0';
        }
        return res;
    }
    void clean()//删除前导零
    {
        while (len > 1 && !s[len - 1]) len--;
    }
    bool operator <(const bign& b) const
    {
        if (len != b.len) return len < b.len;
        for (int i = len - 1; i >= 0; i--)
            if (s[i] != b.s[i]) return s[i] < b.s[i];
        return false;
    }
    bool operator >(const bign& b) const
    {
        if (len != b.len) return len > b.len;
        for (int i = len - 1; i >= 0; i--)
            if (s[i] != b.s[i]) return s[i] > b.s[i];
        return false;
    }
    bool operator ==(const bign& b) const
    {
        if (len != b.len) return false;
        for (int i = len - 1; i >= 0; i--)
            if (s[i] != b.s[i]) return false;
        return true;
    }
    bign operator +(const bign& b)
    {
        bign c;
        c.len = 0;
        for (int i = 0, g = 0; g || i < len || i < b.len; i++)
        {
            int x = g;
            if (i < len) x += s[i];
            if (i < b.len) x += b.s[i];
            c.s[c.len++] = x % 10;
            g = x / 10;
        }
        c.clean();
        return c;
    }
    bign operator-(const bign& T) const {
        int l_len;
        bool ctf;
        bign t1, t2;
        if (*this < T) {
            t1 = T;
            t2 = *this;
            ctf = 1;
        }
        else {
            t1 = *this;
            t2 = T;
            ctf = 0;
        }
        l_len = t1.len;
        int j = 0;
        for (int i = 0; i < l_len; i++) {
            t1.s[i] -= t2.s[i];
            if (t1.s[i] < 0) { t1.s[i + 1]--; t1.s[i] += 10; }
        }
        //len++;
        t1.len = l_len;
        t1.clean();
        if (ctf) t1.s[t1.len - 1] = -t1.s[t1.len - 1];
        return t1;
    }
    bign operator *(const bign& b)
    {
        bign c;
        c.len = len + b.len;
        for (int i = 0; i < len; i++)for (int j = 0; j < b.len; j++)c.s[i + j] += s[i] * b.s[j];
        for (int i = 0; i < c.len - 1; i++) { c.s[i + 1] += c.s[i] / 10; c.s[i] %= 10; }
        c.clean();
        return c;
    }
    bign operator/(const int& b) {//高精/单精
        bign res;
        int down = 0;
        for (int i = len - 1; i >= 0;i--) {
            res.s[i] = (s[i] + down * (10)) / b;
            down = s[i] + down * (10) - res.s[i] * b;
        }
        res.len = len;
        res.clean();
        return res;
    }
    int operator%(const int& b) {//高精%单精
        int d = 0;
        for (int i = len - 1; i >= 0; i--) 
            d = (d * (10) % b + s[i]) % b;
        return d;
    }
    bign operator +=(const bign& b)
    {
        *this = *this + b;
        return *this;
    }
    bign operator -=(const bign& b)
    {
        *this = *this - b;
        return *this;
    }
    friend istream& operator>>(istream& in, bign& x) {
        string s;
        in >> s;
        x = s.c_str();
        return in;
    }
    friend ostream& operator<<(ostream& out, bign& x)
    {
        out << x.str();
        return out;
    }
};

高精度/高精度，高精度%高精度

//arr1为被除数，arr2为被除数，计算后arr为商，arr1为余数
//arr1[0]为arr1的长度，arr2[0]为arr2的长度，arr[0]为arr的长度，temp[0]为temp长度。
#define maxn 100
int arr1[maxn], arr2[maxn], arr[maxn], temp[maxn];
string s1, s2;
int compare(int a[], int b[])//比较a、b，若a>b为1；若a<b为-1；若a=b为0
{
    if (a[0] > b[0]) return 1;
    if (a[0] < b[0]) return -1;
    for (int i = a[0]; i > 0; i--)//从高位到低位比较
    {
        if (a[i] > b[i]) return 1;
        if (a[i] < b[i]) return -1;
    }
    return 0;
}
 
void subduction(int a[], int b[])//计算a=a-b
{
    if (compare(a, b) == 0)//相等
    {
        a[0] = 0;
        return;
    }
    if (compare(a, b) == 1)//大于
    {
        for (int i = 1; i <= a[0]; i++)
        {
            if (a[i] < b[i])//若不够向上借位
            {
                a[i + 1]--;
                a[i] += 10;
            }
            a[i] -= b[i];
        }
        while (a[0] > 0 && a[a[0]] == 0) a[0]--;//删除前导0
    }
}
void division() {
    cin >> s1 >> s2;
    arr1[0] = s1.size();
    arr2[0] = s2.size();
    for (int i = 1; i <= arr1[0]; i++)
        arr1[i] = s1[arr1[0] - i] - '0';
    for (int i = 1; i <= arr2[0]; i++)
        arr2[i] = s2[arr2[0] - i] - '0';
    arr[0] = arr1[0] - arr2[0] + 1;
    for (int i = arr[0]; i > 0; i--)
    {
        memset(temp, 0, sizeof(temp));
        for (int j = 1; j <= arr2[0]; j++)//从i开始的地方，复制数组b到数组temp
            temp[j + i - 1] = arr2[j];
        temp[0] = arr2[0] + i - 1;
 
        while (compare(arr1, temp) >= 0)//减法模拟
        {
            arr[i]++;
            subduction(arr1, temp);
        }
    }
    while (arr[0] > 0 && arr[arr[0]] == 0) arr[0]--;//删除前导0 
//输出
    cout << "商为：";
    if (arr[0] == 0) { arr[1] = 0; arr[0] = 1; }
    for (int i = arr[0]; i > 0; i--)  cout << arr[i]; cout << endl;
    cout << "余数为：";
    if (arr1[0] == 0) { arr1[1] = 0; arr1[0] = 1; }
    for (int i = arr1[0]; i > 0; i--)  cout << arr1[i]; cout << endl;
}
//计算后arr[]为商，arr1[]为余数,arr[0]为arr的长度,arr1[0]为arr1的长度