原代码出处, 转自HDAWN, 经过部分改写, 包装为结构体, 常数比较大.
测试
输出
大概实际操作
具体
支持四则运算及GCD运算, 重写了istream和ostream和比较运算符.
构造函数既可以long long, string, 也可以char[]
如果除法要求余数, a / b = c, a - b * c = res, 除了这样绕一圈, 也可以BI::div(被除数, 除数, 商或余数), 其中第三维为true, 第三维为false.
求余数实际就是取模操作.
缺点:
- 不支持负数, 负数就只能减法
- 注意长度, MaxLen限定长度, 若长度大了, 常数也非常大
- 判小于0, 就是判第一个char是否是'-', 即判x.num.front() == '-'
- 注意二分写法: BI l = "0", r("1" + string(40, '0'));
- 若"1343"这样的char*在参与运算时, 需要显式强制转换
// 不支持负数, 负数就减法; 注意长度; 判小于0, 即判x.num.front() == '-'
// 注意二分写法: BI l = "0", r("1" + string(40, '0'));
// 若"1343"这样的char*在参与运算时, 可能需要显式强制转换
const int MaxLen = 1000;
struct BI {
string num;
static string SBI(long long x) {
string s;
while (x) s += char(x % 10 + '0'), x /= 10;
if (s.empty()) s = "0";
reverse(s.begin(), s.end());
return s;
}
BI() = default;
BI(long long a) : BI(SBI(a)) {}
BI(string B) { num = B; }
BI(const char *s) {
int len = strlen(s);
for (int i = 0; i < len; ++i) num += s[i];
}
friend istream &operator>>(istream &is, BI &rhs) {
is >> rhs.num;
return is;
}
friend ostream &operator<<(ostream &os, const BI &rhs) {
for (auto c : rhs.num) os << c;
return os;
}
char &operator[](int idx) { return num[idx]; }
char operator[](int idx) const { return num[idx]; }
bool operator==(BI rhs) const { return num == rhs.num; }
bool operator!=(BI rhs) const { return !(*this == rhs); }
bool operator<(BI B) const {
if (num.size() != B.num.size()) return num.size() < B.num.size();
for (int i = 0; i < num.size(); ++i)
if (num[i] != B[i]) return num[i] < B[i];
return false;
}
bool operator>(BI rhs) { return rhs < *this; }
bool operator<=(BI rhs) { return !(rhs < *this); }
bool operator>=(BI rhs) const { return !(*this < rhs); }
BI operator+(const BI &B) const {
string ans;
int na[MaxLen] = {0}, nb[MaxLen] = {0};
int la = num.size(), lb = B.num.size(), lmax = max(la, lb);
for (int i = 0; i < la; i++) na[la - 1 - i] = num[i] - '0';
for (int i = 0; i < lb; i++) nb[lb - 1 - i] = B[i] - '0';
for (int i = 0; i < lmax; i++) na[i] += nb[i], na[i + 1] += na[i] / 10, na[i] %= 10;
if (na[lmax]) lmax++;
for (int i = lmax - 1; i >= 0; i--) ans += char(na[i] + '0');
return ans;
}
BI operator+(const long long B) const { return *this + SBI(B); };
BI operator-(BI B) const {
BI A = *this, C;
if (*this < B) {
C = B - *this;
C.num = "-" + C.num;
return C;
}
int la = A.num.size(), lb = B.num.size();
reverse(A.num.begin(), A.num.end()),
reverse(B.num.begin(), B.num.end());
for (int i = 0, t = 0; i < la; i++) {
t = (A[i] - '0') - t;
if (i < lb) t -= B[i] - '0';
C.num += char((t + 10) % 10 + '0');
if (t < 0) t = 1;
else t = 0;
}
while (C.num.size() > 1 && C.num.back() == '0') C.num.pop_back();
reverse(C.num.begin(), C.num.end());
return C;
}
BI operator-(const long long B) const { return *this - SBI(B); };
static int sub(int *a, const int *b, int La, int Lb) {
if (La < Lb) return -1;//如果a小于b，则返回-1
if (La == Lb) {
for (int i = La - 1; i >= 0; i--)
if (a[i] > b[i]) break;
else if (a[i] < b[i]) return -1;//如果a小于b，则返回-1
}
for (int i = 0; i < La; i++) {//高精度减法
a[i] -= b[i];
if (a[i] < 0) a[i] += 10, a[i + 1]--;
}
for (int i = La - 1; i >= 0; i--)
if (a[i]) return i + 1;//返回差的位数
return 0;//返回差的位数
}
BI operator*(const BI &B) const {
string s;
int na[MaxLen]{}, nb[MaxLen]{}, nc[MaxLen]{},
La = num.size(), Lb = B.num.size();//na存储被乘数，nb存储乘数，nc存储积
for (int i = La - 1; i >= 0; i--) na[La - i] = num[i] - '0';//将字符串表示的大整形数转成i整形数组表示的大整形数
for (int i = Lb - 1; i >= 0; i--) nb[Lb - i] = B[i] - '0';
for (int i = 1; i <= La; i++) {//a的第i位乘以b的第j位为积的第i+j-1位（先不考虑进位）
for (int j = 1; j <= Lb; j++) nc[i + j - 1] += na[i] * nb[j];
}
for (int i = 1; i <= La + Lb; i++) nc[i + 1] += nc[i] / 10, nc[i] %= 10;//统一处理进位
if (nc[La + Lb]) s += char(nc[La + Lb] + '0');//判断第i+j位上的数字是不是0
for (int i = La + Lb - 1; i >= 1; i--) s += char(nc[i] + '0');//将整形数组转成字符串
return s;
}
BI operator*(const long long B) const { return *this * SBI(B); };
static BI div(BI n1, BI n2, bool fl) {// true返回商, false余数
string s, v;// s存商,v存余数
int a[MaxLen]{}, b[MaxLen]{}, r[MaxLen]{},
La = n1.num.size(), Lb = n2.num.size(), tp = La;
//a，b是整形数组表示被除数，除数，tp保存被除数的长度
for (int i = La - 1; i >= 0; i--) a[La - 1 - i] = n1[i] - '0';
for (int i = Lb - 1; i >= 0; i--) b[Lb - 1 - i] = n2[i] - '0';
//如果a<b,则商为0，余数为被除数
if (La < Lb || (La == Lb && n1 < n2)) return (fl ? "0" : n1);
int t = La - Lb;//除被数和除数的位数之差
for (int i = La - 1; i >= 0; i--)//将除数扩大10^t倍
if (i >= t) b[i] = b[i - t];
else b[i] = 0;
Lb = La;
for (int i = 0; i <= t; i++) {
int temp;//如果被除数比除数大继续减
while ((temp = sub(a, b + i, La, Lb - i)) >= 0) {
La = temp;
r[t - i]++;
}
}
int p;
for (p = 0; p < MaxLen - 10; p++) r[p + 1] += r[p] / 10, r[p] %= 10;//统一处理进位
while (!r[p]) p--;//将整形数组表示的商转化成字符串表示的
while (p >= 0) s += char(r[p--] + '0');
p = tp;
while (!a[p]) p--;//将整形数组表示的余数转化成字符串表示的</span>
while (p >= 0) v += char(a[p--] + '0');
if (v.empty()) v = "0";
return (fl ? s : v);
}
BI operator/(BI n2) const { return div(*this, n2, true); }
BI operator/(const long long B) const { return *this / SBI(B); };
static bool jud(const string &s) {//判断s是否为全0串
for (char i : s) if (i != '0') return false;
return true;
}
static BI gcd(BI a, BI b) {
BI t;//如果余数不为0，继续除
while (!jud(b.num)) {
t = a;//保存被除数的值
a = b;//用除数替换被除数
b = div(t, b, false);//用余数替换除数
}
return a;
}
};
BI gcd(BI &A, BI &B) { return BI::gcd(A, B); }
// 不支持负数, 负数就减法; 注意长度; 判小于0, 即判x.num.front() == '-'
// 注意二分写法: BI l = "0", r("1" + string(40, '0'));
// 若"1343"这样的char*在参与运算时, 可能需要显式强制转换