题目描述#

两个数两行

$A \ B$

输入格式#

五个数

和 差 积 商 余

输出格式#

输入输出样例#

1
1

2
0
1
1
0

说明/提示#

$leng(A),leng(B)<=10^4$

$A,B>0$ 每个点 $3s$。

原理#

用数组模拟高精度类型，如1024可以表示成：

索引：
+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 |
+---+---+---+---+---+

内容：
+---+---+---+---+---+
| 4 | 4 | 2 | 0 | 1 |
+---+---+---+---+---+

可知数组第 $0$ 位存的是该大整数的位数，然后从个位依次往后存储每一位数字。

声明#

由此可声明大整数类bigint如下：

class bigint
{
private:
    bool minus;
    int num[maxn];

public:
    bigint();
    bigint(const int &n);
    operator int() const;
    void read();
    void print() const;

    bool operator<(const bigint &x) const;
    bool operator<=(const bigint &x) const;
    bool operator!=(const bigint &x) const;
    bool operator==(const bigint &x) const;
    bool operator>(const bigint &x) const;
    bool operator>=(const bigint &x) const;

    bigint operator+(const bigint &x) const;
    bigint operator-() const;
    bigint operator-(const bigint &x) const;
    bigint operator*(const bigint &x) const;
    bigint operator/(const bigint &x) const;
    bigint operator%(const bigint &x) const;
    bigint operator=(const int &x);

    bigint abs() const;
};

输入输出#

先是bigint类型的初始化和输入输出：

bigint::bigint()    //bigint初始化为正0
{
    minus = false;
    memset(num, 0, sizeof(num));
    num[0] = 1;
}

void bigint::read()
{
    memset(num, 0, sizeof(num));
    char s[maxn];
    scanf("%1s", s + 1);
    if (s[1] == '-')    //读入时先判断是不是负数
    {
        minus = true;
        scanf("%s", s + 1);
    }
    else
    {
        scanf("%s", s + 2);
    }
    num[0] = strlen(s + 1);
    for (int i = 1; i <= num[0]; i++)
    {
        num[i] = s[num[0] - i + 1] - '0';
    }
}

void bigint::print()
{
    if (minus)
        printf("-");
    for (int i = num[0]; i >= 1; i--)
    {
        printf("%d", num[i]);
    }
}

比较运算#

由于高精度减法需要用到大整数的比较运算，不妨先写一下比较运算。比较运算看似有<， <=, !=, ==, >, >=这六类，但实际上只需要写<和==就可以了，原因如下：

因此只需要写好<和==的重载，其他比较运算符只需要调用已有接口即可。

bool bigint::operator<(const bigint &b) const
{
    if (minus != b.minus)
        return minus > b.minus;
    if (num[0] != b.num[0])
        return num[0] < b.num[0];
    for (int i = num[0]; i >= 1; i--)
    {
        if (num[i] != b.num[i])
            return num[i] <= b.num[i];
    }
    return false;
}

bool bigint::operator<=(const bigint &b) const
{
    if (*this < b || *this == b)
        return true;
    else
        return false;
}

bool bigint::operator!=(const bigint &b) const
{
    if (*this < b || b < *this)
        return true;
    else
        return false;
}

bool bigint::operator==(const bigint &b) const
{
    if (minus != b.minus)
        return false;
    if (num[0] != b.num[0])
        return false;
    for (int i = num[0]; i >= 1; i--)
    {
        if (num[i] != b.num[i])
            return false;
    }
    return true;
}

bool bigint::operator>=(const bigint &b) const
{
    if (b < *this || b == *this)
        return true;
    else
        return false;
}

bool bigint::operator>(const bigint &b) const
{
    if (b < *this)
        return true;
    else
        return false;
}

取绝对值、取相反数与强制类型转换#

再顺便写一下取相反数，绝对值和int与bigint的互相转化。这里重载了int强制类型转换，同时对于int向bigint的转换，采取的 Modern C++所倡导的形如bigint(x)样式的显式转换，而非(bigint)x样式的传统 C 语言强制类型转换，以保证安全性。

bigint::bigint(const int &n)
{
    int tmp = n;
    minus = tmp < 0;
    memset(num, 0, sizeof(num));
    while (tmp > 0)
    {
        num[++num[0]] = tmp % 10;
        tmp /= 10;
    }
    if (num[0] == 0)
        num[0] = 1;
}

bigint::operator int() const
{
    int n = 0;
    for (int i = num[0]; i >= 1; i--)
    {
        n *= 10;
        n += num[i];
    }
    return n;
}


bigint bigint::operator-() const
{
    bigint c = *this;
    c.minus ^= 1;
    return c;
}

bigint bigint::abs() const
{
    bigint c = *this;
    if (c < bigint(0))
        c = (-c);
    return c;
}

四则运算#

至此正式写高精前的准备工作就完成了。

事实上高精度算法的本质是模拟人工列竖式计算的过程。如加法的做法是输入的两个数，按位相加，然后模拟进位即可。

然而不论加减乘除，我们都希望把复杂的情况转化为几种基本情况，比如加法中我们总是希望两个正数相加，减法中总是两个正数相减，且结果为正。

加法#

对于加法来说，有这些情况：

• $a < 0, \ b > 0$ ，则 $a + b = b - (-a))$
• $a < 0, \ b < 0$ ，则 $a + b = - ( (-a) + (-b) )$
• $a > 0, \ b > 0$ ，则 $a + b = a + b$
• $a > 0, \ b < 0$ ，则 $a + b = a - (-b)$

bigint bigint::operator+(const bigint &x) const
{

    if ((*this) == bigint(0))
        return x;
    if (x == bigint(0))
        return *this;

    if (*this < bigint(0) && x > bigint(0))
        return x - (*this).abs();
    if (*this < bigint(0) && x < bigint(0))
        return -((*this).abs() + x.abs());
    if (*this > bigint(0) && x < bigint(0))
        return (*this) - x.abs();

    bigint a = *this, b = x, c;
    c.num[0] = max(a.num[0], b.num[0]);
    for (int i = 1; i <= c.num[0]; i++)
    {
        c.num[i] += a.num[i] + b.num[i];
        c.num[i + 1] += c.num[i] / 10;
        c.num[i] %= 10;
    }
    if (c.num[c.num[0] + 1])
        c.num[0]++;
    return c;
}

减法#

减法稍微复杂一点，我们应该尽量将其转换成两个正数的加减法操作，可以分几种情况判断：

• $a < 0, \ b > 0$ ，则 $a - b = - ((-a) + b)$
• $a < 0, \ b < 0$ ，则 $a - b = (-b) - (-a)$
• $a > 0, \ b > 0$ ，则 $a - b = a - b$
• $a > 0, \ b < 0$ ，则 $a - b = a + (-b)$

bigint bigint::operator-(const bigint &x) const
{
    bigint a = *this, b = x, c;
    if (a == bigint(0))
        return -b;
    if (b == bigint(0))
        return a;

    if (a < bigint(0) && b > bigint(0))
        return -(-a + b);
    if (a < bigint(0) && b < bigint(0))
        return (-b) - (-a);
    if (a > bigint(0) && b < bigint(0))
        return a + (-b);

    if (a < b)
    {
        c.minus ^= 1;
        swap(a, b);
    }

    c.num[0] = a.num[0];
    for (int i = 1; i <= c.num[0]; i++)
    {
        c.num[i] = a.num[i] - b.num[i];
    }
    for (int i = 1; i <= c.num[0]; i++)
    {
        if (c.num[i] < 0)
        {
            c.num[i + 1] -= 1;
            c.num[i] += 10;
        }
    }
    while (!c.num[c.num[0]])
    {
        if (c.num[0] == 1)
            break;
        c.num[0]--;
    }

    return c;
}

乘法#

乘法需要注意的是，对于数 $a, \ b$ ， $a$ 的第 $i$ 位与 $b$ 的第 $j$ 之积对结果的第 $i + j - 1$ 位有贡献，计算过程中注意实时向第 $i + j$ 位进位。正负号方面， 符号不同为负，相同为正。

bigint bigint::operator*(const bigint &x) const
{
    bigint a = *this, b = x, c;
    if (a.abs() < b.abs())
        swap(a, b);
    c.minus = a.minus ^ b.minus;
    c.num[0] = a.num[0] + b.num[0];
    for (int j = 1; j <= b.num[0]; j++)
    {
        for (int i = 1; i <= a.num[0]; i++)
        {
            c.num[i + j - 1] += a.num[i] * b.num[j];
            c.num[i + j] += c.num[i + j - 1] / 10;
            c.num[i + j - 1] %= 10;
        }
    }
    while (!c.num[c.num[0]])
    {
        if (c.num[0] == 1)
        {
            c = bigint(0);
            break;
        }
        c.num[0]--;
    }
    return c;
}

除法#

除法同样是模拟竖式，不同的是，这里不纠结于商究竟是几位数字，而直接从最高位开始试除。高精度除法需要依赖高精度加、减、乘法。

bigint bigint::operator/(const bigint &x) const
{
    bigint a = *this, b = x, c, tmp, cnt;
    bool flag = a.minus ^ b.minus;
    // c.minus = ;
    a = a.abs();
    b = b.abs();
    tmp.num[0] = a.num[0];
    tmp.num[tmp.num[0]] = 1;
    while (a > b)
    {
        cnt = bigint(0);
        while (b * tmp * (cnt + bigint(1)) <= a)
            cnt = cnt + bigint(1);
        c = c + tmp * cnt;
        a = a - b * tmp * cnt;
        tmp.num[tmp.num[0]] = 0;
        tmp.num[0]--;
        tmp.num[tmp.num[0]] = 1;
    }
    if (!(c.num[0] == 1 && c.num[1] == 0))
        c.minus = flag;
    return c;
}

取模#

取模计算也很简单， $b$ 对 $a$ 取模的结果就是 $a - \lfloor a / b \rfloor * b$

bigint bigint::operator%(const bigint &x) const
{
    bigint a = *this, b = x;
    return a - a / b * b;
}