题解 P1932 【A+B A-B A*B A/B A%B Problem】
DEVILK
2018-05-05 21:20:24
BIGNUM大整数型压位（可修改压位数及最大数字长度）
除法用了倍增优化
压到八位的时候应把整型数组开成long long
因为八位的时候进行大整数相乘时会爆掉int
开了long long压八位之后，相比于开int压四位，空间没有优化
但是却可以提高算法的时间效率
还有一种不大常规但是效果很显著的优化：
开了long long后最多可以压位压到9位
比long long压8位和int压4位都要快，消耗的内存少.
各种重载运算符（+、-、*、/、%、>>、<<）
写起来有点繁琐~~（200行好吓人）~~但用起来很简便
------------
虽然有人写过重载运算符了，但是并没有重载/
这个BIGNUM大整数型封装的很完美，既有压位（9位而且可以修改），又有倍增优化的高精度除法
求通过
------------
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
static const int LEN = 10000 + 1;
struct BIGNUM {
//不定义成全局常量，方便移植BIGNUM类
static const int BIT = 9;//压位位数
static const int MOD = 1000000000;//1eBIT
long long s[LEN];
bool flag;//负数的话flag为false
BIGNUM() {
memset(s, 0, sizeof(s));
flag = s[0] = 1;
}
void init() {
memset(s, 0, sizeof(s));
s[0] = 1;
}
//压位的特殊处理
//从后向前每BIT个数字放在一组
BIGNUM operator = (const char *num) {
int l = strlen(num);
s[0] = 0;
for(int i = l - 1; i >= 0; i -= BIT) {
++s[0];
long long w = 1;
for(int j = i; j > i - BIT && j >= 0; j--) {
s[s[0]] += (num[j] ^ 48) * w;
w = (w << 1) + (w << 3);
}
}
return *this;
}
BIGNUM operator = (const int num) {
char a[LEN];
sprintf(a, "%d", num);
*this = a;
return *this;
}
BIGNUM(int num) { *this = num; }
BIGNUM(const char *num) { *this = num; }
BIGNUM operator + (const BIGNUM &a) {
BIGNUM c;
int x = 0;
c.s[0] = max(a.s[0], s[0]) + 1;
for(int i = 1; i <= c.s[0]; i++) {
c.s[i] = a.s[i] + s[i] + x;
//压位其实就是把/10变成了/MOD
//%10变成了%MOD
x = c.s[i] / MOD;
c.s[i] %= MOD;
}
while(c.s[c.s[0]] == 0 && c.s[0] > 1) c.s[0]--;
return c;
}
BIGNUM operator += (const BIGNUM &a) {
*this = *this + a;
return *this;
}
//重载逻辑关系运算符
bool operator == (const BIGNUM &a) {
int up = max(s[0], a.s[0]);
for(int i = 0; i < up; i++)
if(s[up - i] != a.s[up - i]) return false;
return true;
}
bool operator > (const BIGNUM &a) {
if(s[0] != a.s[0]) return s[0] > a.s[0];
int up = max(s[0], a.s[0]);
for(int i = 0; i < up; i++)
if(s[up - i] != a.s[up - i]) return s[up - i] > a.s[up - i];
return false;
}
bool operator < (const BIGNUM &a) {
if(s[0] != a.s[0]) return s[0] < a.s[0];
int up = max(s[0], a.s[0]);
for(int i = 0; i < up; i++)
if(s[up - i] != a.s[up - i]) return s[up - i] < a.s[up - i];
return false;
}
bool operator >= (const BIGNUM &a) {
if(*this > a || *this == a) return true;
return false;
}
bool operator <= (const BIGNUM &a) {
if(*this < a || *this == a) return true;
return false;
}
BIGNUM operator - (const BIGNUM &a) {
BIGNUM c;
c.s[0] = max(a.s[0], s[0]) + 1;
if(*this < a) c.flag = false;
for(int i = 1; i <= c.s[0]; i++) {
if(c.flag) c.s[i] += s[i] - a.s[i];
else c.s[i] += a.s[i] - s[i];
if(c.s[i] < 0) {
c.s[i] += MOD;
c.s[i + 1]--;
}
}
//除去多余的前导零
while(c.s[c.s[0]] == 0 && c.s[0] > 1) c.s[0]--;
return c;
}
BIGNUM operator -= (const BIGNUM &a) {
*this = *this - a;
return *this;
}
BIGNUM operator * (const BIGNUM &a) {
BIGNUM c;
c.s[0] = s[0] + a.s[0];
for(int i = 1; i <= s[0]; i++) {
int x = 0;
for(int j = 1; j <= a.s[0]; j++) {
c.s[i + j - 1] += s[i] * a.s[j] + x;
x = c.s[i + j - 1] / MOD;
c.s[i + j - 1] %= MOD;
}
c.s[i + a.s[0]] = x;
}
while(c.s[c.s[0]] > 0) c.s[0]++;
while(c.s[c.s[0]] == 0 && c.s[0] > 1) c.s[0]--;
return c;
}
BIGNUM operator *= (const BIGNUM &a) {
*this = *this * a;
return *this;
}
//重载左移右移运算符
//倍增优化减法模拟的除法时需要用
BIGNUM operator << (const int &num) {
s[0]++;
for(int i = 1; i <= s[0]; i++) {
s[i] <<= num;
if(s[i - 1] >= MOD)
s[i - 1] -= MOD, ++s[i];
}
while(s[s[0]] == 0 && s[0] > 1) s[0]--;
return *this;
}
BIGNUM operator >> (const int &num) {
for(int i = s[0]; i >= 1; i--) {
if((s[i] & 1) && i > 1) s[i - 1] += MOD;
s[i] >>= num;
}
while(s[s[0]] == 0 && s[0] > 1) s[0]--;
return *this;
}
BIGNUM operator / (const BIGNUM &k) {
BIGNUM c = *this, tmp, lt, a;
a = k;
tmp.s[1] = 1;
//找到小于等于c的a
//使用倍增优化，每次*2
//复杂度降到了log
//倍增优化楼下
//明月の卫——AH 已经说的很详细了，不多说
while(c >= a) {
a = a << 1;
tmp = tmp << 1;
}
while(tmp.s[0] > 1 || tmp.s[1]) {
if(c >= a) {
c -= a;
lt += tmp;
}
a = a >> 1;
tmp = tmp >> 1;
}
c = lt;//a为当前余数
while(c.s[c.s[0]] == 0 && c.s[0] > 1) c.s[0]--;
if(c.s[0] < 1) c.s[c.s[0] = 1] = 0;
return c;
}
BIGNUM operator /= (const BIGNUM &a) {
*this = *this / a;
return *this;
}
//虽然做除法的时同时求出了商和余数
//但是返回的只是商的值
//所以还要重载 mod 运算
BIGNUM operator % (const BIGNUM &a) {
BIGNUM d = *this, c = *this / a;
c *= a;
return d - c;
}
BIGNUM operator %= (const BIGNUM &a) {
*this = *this % a;
return *this;
}
};
//重载读入读出
ostream& operator << (ostream &out, const BIGNUM &a) {
if(!a.flag) putchar('-');
//读出时先把第一组BIT位数输出
//之后的每一组数不足BIT位的要在左边补零
printf("%d", a.s[a.s[0]]);
for(int i = a.s[0] - 1; i >= 1; i--)
printf("%09d", a.s[i]);
return out;
}
istream& operator >> (istream &in, BIGNUM &a) {
char str[LEN];
in >> str;
a = str;
return in;
}
BIGNUM a, b;
int main() {
cin >> a >> b;
cout << a + b << endl;
cout << a - b << endl;
cout << a * b << endl;
cout << a / b << endl;
cout << a % b << endl;
}
```
附博客链接：
[内含普通高精度，压位高精度和BIGNUM大整数型](http://www.cnblogs.com/devilk-sjj/p/8992281.html)