高精模板

· · 个人记录

高精模板

这是一套高精模板，它可以支持整数+, -, *, /, % 运算，同时还可以支持>, <, ≥(>=), ≤(<=), =(==), ≠(!=)的判断，以及低精转换高精，甚至还可以实现快速幂，开根的功能。

你只需要像平时一样直接加入运算符即可。

例如我需要计算两个高精数相加的和，我需要做以下步骤：

  1. 定于两个高精变量
Bignum a, b;
  1. 读入这两个高精变量
a.read();
b.read();
  1. 把两数相加，并赋值给答案变量c
Bignum c = a + b;
  1. 输出答案变量
c.write();

其他运算也是如此。

同时还可以比较大小，例如：

Bignum a, b;
if (a > b) {
    b = a; //将b赋值为a, b中较大值
}

低精转换高精：

int a;
Bignum b = change(a);

高精快速幂：

Bignum a, b;
a = a.Power(b);

高精开根：

Bignum a, b;
a = a.Sqrt(b);

高精的位数如果开大，本地运行会无法运行，但是在洛谷上可以运行，所以请放心提交。

高精快速幂与高精开根请慎用，容易超时。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 10010;
struct Bignum {
    int num[N];
    bool compare (const Bignum a, const Bignum b) {
        int len1 = a.num[0], len2 = b.num[0], flag;
        if (len1 > 0 && len2 > 0) flag = 1;
        else if (len1 < 0 && len2 < 0) flag = 2;
        else {
            if (len1 > 0 && len2 < 0) return true;
            else return false;
        }
        len1 = len1 < 0 ? - len1 : len1;
        len2 = len2 < 0 ? - len2 : len2;
        if (flag == 1) {
            if (len1 > len2) return true;
            else if (len1 < len2) return false;
            else {
                for (int i = len1; i >= 1; i --) {
                    if (a.num[i] > b.num[i]) return true;
                    else if (a.num[i] < b.num[i]) return false;
                }
                return true;
            }
        } else {
            if (len1 > len2) return false;
            else if (len1 < len2) return true;
            else {
                for (int i = len1; i >= 1; i --) {
                    if (a.num[i] > b.num[i]) return false;
                    else if (a.num[i] < b.num[i]) return true;
                }
                return true;
            }
        }
    }
    Bignum change (long long a) {
        Bignum ans;
        memset(ans.num, 0, sizeof(ans.num));
        long long x = a < 0 ? - a : a;
        while (x) {
            ans.num[++ ans.num[0]] = x % 10;
            x /= 10;
        }
        if (a < 0) ans.num[0] = - ans.num[0];
        if (!a)
            ans.num[0] = 1;
        return ans;
    }
    bool operator > (const Bignum &a) {
        if (!compare(a, *this)) return true;
        else return false;
    }
    bool operator < (const Bignum &a) {
        if (!compare(*this, a)) return true;
        else return false;
    }
    bool operator >= (const Bignum &a) {
        if (compare(*this, a)) return true;
        else return false;
    }
    bool operator <= (const Bignum &a) {
        if (compare(a, *this)) return true;
        else return false;
    }
    bool operator == (const Bignum &a) {
        if (compare(*this, a) && compare(a, *this)) return true;
        else return false;
    }
    bool operator != (const Bignum &a) {
        if (compare(*this, a) && compare(a, *this)) return false;
        else return true;
    }
    Bignum add (const Bignum &a, const Bignum &b) {
        Bignum ans = change(0);
        int len1 = a.num[0], len2 = b.num[0], len;
        len1 = len1 < 0 ? - len1 : len1;
        len2 = len2 < 0 ? - len2 : len2;
        len = max(len1, len2) + 1;
        int x = 0;
        for (int i = 1; i <= len; i ++) {
            ans.num[i] = a.num[i] + b.num[i] + x;
            x = ans.num[i] / 10;
            ans.num[i] %= 10;
        }
        while (len > 1 && !ans.num[len]) len --;
        ans.num[0] = len;
        return ans;
    }
    Bignum minus (const Bignum &a, const Bignum &b) {
        Bignum ans = change(0);
        int len1 = a.num[0], len2 = b.num[0], len;
        len1 = len1 < 0 ? - len1 : len1;
        len2 = len2 < 0 ? - len2 : len2;
        len = max(len1, len2);
        int x = 0;
        for (int i = 1; i <= len; i ++) {
            ans.num[i] = a.num[i] - b.num[i] + x;
            if (ans.num[i] < 0) {
                ans.num[i] += 10;
                x = -1;
            } else
                x = 0;
        }
        while (len > 1 && !ans.num[len]) len --;
        ans.num[0] = len;
        return ans;
    }
    Bignum multiply (const Bignum &a, const Bignum &b) {
        Bignum ans = change(0);
        int len1 = a.num[0], len2 = b.num[0], len;
        len1 = len1 < 0 ? - len1 : len1;
        len2 = len2 < 0 ? - len2 : len2;
        len = len1 + len2;
        for (int i = 1; i <= len1; i ++) {
            int x = 0;
            for (int j = 1; j <= len2; j ++) {
                ans.num[i + j - 1] += a.num[i] * b.num[j] + x;
                x = ans.num[i + j - 1] / 10;
                ans.num[i + j - 1] %= 10;
            }
            ans.num[len2 + i] += x;
        }
        while (len > 1 && !ans.num[len]) len --;
        ans.num[0] = len;
        return ans;
    }
    Bignum divide (const Bignum &a, const Bignum &b, int flag) {
        Bignum ans = change(0), tmp1, tmp2;
        tmp1 = a;
        tmp2 = b;
        int len1 = a.num[0], len2 = b.num[0], len;
        len1 = len1 < 0 ? - len1 : len1;
        len2 = len2 < 0 ? - len2 : len2;
        len = len1 - len2 + 1;
        tmp1.num[0] = len1;
        tmp2.num[0] = len2;
        for (int i = 1; i < len; i ++) tmp2 = multiply(tmp2, change(10));
        for (int i = len; i >= 1; i --) {
            while (tmp1 >= tmp2) {
                tmp1 = minus(tmp1, tmp2);
                ans.num[i] ++;
            }
            for (int j = 1; j < tmp2.num[0]; j ++)
                tmp2.num[j] = tmp2.num[j + 1];
            tmp2.num[tmp2.num[0] --] = 0;
        }
        while (len > 1 && !ans.num[len]) len --;
        ans.num[0] = len;
        if (flag == 1) return ans;
        else return tmp1;
    }
    Bignum operator + (const Bignum &a) {
        Bignum tmp, tmp1, tmp2;
        if (num[0] > 0 && a.num[0] > 0)
            tmp = add(*this, a);
        else if (num[0] < 0 && a.num[0] < 0) {
            tmp = add(*this, a);
            tmp.num[0] = - tmp.num[0];
        } else {
            tmp1 = *this, tmp2 = a;
            if (num[0] < 0) {
                tmp1.num[0] = - tmp1.num[0];
                if (tmp1 > tmp2) {
                    tmp = minus(tmp1, tmp2);
                    tmp.num[0] = - tmp.num[0];
                } else
                    tmp = minus(tmp2, tmp1);
            } else {
                tmp2.num[0] = - tmp2.num[0];
                if (tmp1 > tmp2)
                    tmp = minus(tmp1, tmp2);
                else {
                    tmp = minus(tmp2, tmp1);
                    tmp.num[0] = - tmp.num[0];
                }
            }
        }
        return tmp;
    }
    Bignum operator - (const Bignum &a) {
        Bignum tmp;
        if (num[0] > 0 && a.num[0] > 0) {
            if (*this >= a)
                tmp = minus(*this, a);
            else {
                tmp = minus(a, *this);
                tmp.num[0] = - tmp.num[0];
            }
        } else if (num[0] < 0 && a.num[0] < 0) {
            if (*this >= a)
                tmp = minus(a, *this);
            else {
                tmp = minus(*this, a);
                tmp.num[0] = - tmp.num[0];
            }
        } else {
            if (num[0] < 0) {
                tmp = add(*this, a);
                tmp.num[0] = - tmp.num[0];
            } else
                tmp = add(*this, a);
        }
        return tmp;
    }
    Bignum operator * (const Bignum &a) {
        Bignum tmp;
        if (num[0] > 0 && a.num[0] > 0)
            tmp = multiply(*this, a);
        else if (num[0] < 0 && a.num[0] < 0)
            tmp = multiply(*this, a);
        else {
            tmp = multiply(*this, a);
            tmp.num[0] = - tmp.num[0];
        }
        return tmp;
    }
    Bignum operator / (const Bignum &a) {
        Bignum tmp, tmp1, tmp2;
        tmp1 = *this;
        tmp2 = a;
        if (num[0] < 0) tmp1.num[0] = - tmp1.num[0];
        if (a.num[0] < 0) tmp2.num[0] = - tmp2.num[0];
        if (tmp1 < tmp2)
            tmp = change(0);
        else {
            if (num[0] > 0 && a.num[0] > 0)
                tmp = divide(*this, a, 1);
            else if (num[0] < 0 && a.num[0] < 0)
                tmp = divide(*this, a, 1);
            else {
                tmp = divide(*this, a, 1);
                tmp.num[0] = - tmp.num[0];
            }
        }
        return tmp;
    }
    Bignum operator % (const Bignum &a) {
        Bignum tmp, tmp1, tmp2;
        tmp1 = *this;
        tmp2 = a;
        if (num[0] < 0) tmp1.num[0] = - tmp1.num[0];
        if (a.num[0] < 0) tmp2.num[0] = - tmp2.num[0];
        if (tmp1 < tmp2)
            tmp = tmp1;
        else {
            tmp = divide(tmp1, tmp2, 2);
            if (tmp != change(0) && num[0] < 0) tmp.num[0] = - tmp.num[0];
        }
        return tmp;
    }
    Bignum Power (const Bignum &a) {
        Bignum res = change(1), tmp1 = *this, tmp2 = a;
        while (tmp2 != change(0)) {
            if (tmp2.num[1] % 2 == 1) res = res * tmp1;
            tmp1 = tmp1 * tmp1;
            tmp2 = tmp2 / change(2);
        }
        return res;
    }
    Bignum Sqrt (const Bignum &a) {
        Bignum l = change(1), r = *this, mid;
        while (l <= r) {
            mid = (l + r) / change(2);
            if (mid.Power(a) <= *this)
                l = mid + change(1);
            else
                r = mid - change(1);
        }
        return r;
    }
    void read () {
        memset(num, 0, sizeof(num));
        char ch = getchar();
        int flag = 1, len = 0;
        Bignum tmp;
        while (ch < '0' || ch > '9') {
            if (ch == '-') flag = -1;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            tmp.num[++ len] = ch - '0';
            ch = getchar();
        }
        for (int i = 1; i <= len; i ++)
            num[i] = tmp.num[len - i + 1];
        if (flag == -1) len = - len;
        num[0] = len;
    }
    void write () {
        int len;
        if (num[0] < 0) {
            putchar('-');
            len = - num[0];
        } else
            len = num[0];
        for (int i = len; i >= 1; i --)
            putchar(num[i] + 48);
        printf("\n");
    }
};
Bignum change (long long a) {
    Bignum ans;
    memset(ans.num, 0, sizeof(ans.num));
    long long x = a < 0 ? - a : a;
    while (x) {
        ans.num[++ ans.num[0]] = x % 10;
        x /= 10;
    }
    if (a < 0) ans.num[0] = - ans.num[0];
    if (!a)
        ans.num[0] = 1;
    return ans;
}
int main () {
    return 0;
}