高精度模板(只可以处理正数)
source: 大佬的高精全模板
结构体重载高精度
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int base = 1e8;
const int N = 1e4 + 10;
int aux[N << 3];
struct bigint {
int s[N], l;
void clear() { l = 0; memset(s, 0, sizeof(s)); }
void print(){
printf("%d", s[l]);
for (int i = l - 1; i; -- i) printf("%08d", s[i]);
}
void read(){
int i, x = 0, k = 1, L = 0, fl, o;
char c = getchar();
for(; c < '0' || c > '9'; c = getchar());
for(; c >= '0' && c <= '9'; c = getchar()){
if(!(L - 1) && !aux[L])L--;
aux[++L] = c - '0';
}
clear(); l = L / 8 + ((o = L % 8) > 0);
for (i = 1; i <= o; ++ i) x = x * 10 + aux[i];
if (o) s[l] = x;
fl = !o ? l + 1 : l;
for (i = o + 1, x = 0; i <= L; ++ i, ++ k){
x = x * 10 + aux[i];
if(!(k ^ 8)) s[--fl] = x,x = k = 0;
}
if(!l) l = 1;
}
LL toint(){
LL x = 0;
for(int i = l; i; -- i)x = x * base + s[i];
return x;
}
bigint operator = (int b){
clear();
do s[++l] = b % base,b /= base;while (b > 0);
return *this;
}
bigint operator = (LL b){
clear();
do s[++l] = b % base,b /= base;while (b > 0);
return *this;
}
bigint operator + (const int &b){
bigint c = *this;
LL x = b;
for (int i = 1; i <= l && x; ++ i){
x = x + c.s[i];
c.s[i] = x % base;
x /= base;
}
if (x)c.s[++c.l] = x;
return c;
}
bigint operator + (const LL &b){
bigint c = *this;
LL x = b;
for (int i = 1; i <= l && x; ++ i){
x = x + c.s[i];
c.s[i] = x % base;
x /= base;
}
if (x)c.s[++c.l] = x;
return c;
}
bigint operator + (bigint &b){
if (b.l < 3)return *this + b.toint();
bigint c;LL x = 0;
int k = l < b.l ? b.l : l;
c.clear(),c.l = k;
for (int i = 1; i <= k; ++ i){
x = x + s[i] + b.s[i];
c.s[i] = x % base;
x /= base;
}
if (x)c.s[++c.l] = x;
return c;
}
bigint operator - (const bigint &b){
bigint c, d = *this;
LL x = 0;c.clear();
for (int i = 1; i <= l; ++ i){
if((x = d.s[i]) < b.s[i])d.s[i + 1]--,x += base;
c.s[i] = x - b.s[i];
}
c.l = l;
for(; !c.s[c.l] && c.l > 1; c.l--);
return c;
}
bigint operator - (const int &b){bigint c;return *this - (c = b);}
bigint operator - (const LL &b){bigint c;return *this - (c = b);}
bigint operator * (const int &b){
bigint c;LL x = 0;c.clear();
for (int i = 1; i <= l; ++ i){
x = x + 1LL * s[i] * b;
c.s[i] = x % base;
x /= base;
}
for (c.l = l; x; x /= base)c.s[++c.l] = x % base;
return c;
}
bigint operator * (bigint &b){
if (b.l < 2)return *this * b.toint();
bigint c;LL x;int i, j, k;c.clear();
for (i = 1; i <= l; ++ i){
x=0;
for (j = 1; j <= b.l; j++){
x = x + 1LL * s[i] * b.s[j] + c.s[k = i + j - 1];
c.s[k] = x % base;
x /= base;
}
if (x)c.s[i + b.l] = x;
}
for (c.l = l + b.l; !c.s[c.l] && c.l > 1; c.l--);
return c;
}
bigint operator * (const LL &b){
bigint c;
if (b > 2e9){c = b;return *this * c;}
LL x = 0;c.clear();
for(int i = 1; i <= l; ++ i){
x = x + b * s[i];
c.s[i] = x % base;
x /= base;
}
for(c.l = l; x; x /= base)c.s[++c.l] = x % base;
return c;
}
bigint operator / (const int &b){
bigint c;LL x = 0;c.clear();
for (int i = l; i; -- i){
c.s[i] = (x * base + s[i]) / b;
x = (x * base + s[i]) % b;
}
for (c.l = l; !c.s[c.l] && c.l > 1; c.l--);
return c;
}
bigint operator / (const LL &b){
bigint c;LL x = 0;c.clear();
for (int i = l; i; -- i){
c.s[i] = (x * base + s[i]) / b;
x = (x * base + s[i]) % b;
}
for (c.l = l; !c.s[c.l] && c.l > 1; c.l--);
return c;
}
bigint operator / (bigint &b){
if (b.l < 2)return *this / b.toint();
bigint c, d;int i, j, le, r, mid, k;c.clear();d.clear();
for (i = l; i; -- i){
for (j = ++d.l; j > 1; j--)d.s[j] = d.s[j - 1];
d.s[1] = s[i];
if (d < b)continue;
le = k = 0;r = base - 1;
while (le <= r){
mid = (le + r) >> 1;
if (b * mid <= d)le = mid + 1,k = mid;
else r = mid - 1;
}
c.s[i] = k,d=d-b * k;
}
for (c.l = l; !c.s[c.l] && c.l > 1; c.l--);
return c;
}
bigint operator % (const int &b){
bigint c;LL x = 0;c.clear();
for (int i = l; i; -- i)x = (x * base + s[i]) % b;
return c = x;
}
bigint operator % (const LL &b){
bigint c;LL x = 0;c.clear();
for (int i = l; i; -- i)x = (x * base + s[i]) % b;
return c = x;
}
bigint operator % (bigint &b){
if (b.l < 2)return *this % b.toint();
bigint c;int i, j, le, r, mid, k;c.clear();
for (i = l; i; -- i){
for (j = ++c.l; j > 1; j--)c.s[j] = c.s[j - 1];
c.s[1] = s[i];
if (c < b)continue;
le = k = 0,r = base - 1;
while (le <= r){
mid = (le + r) >> 1;
if (b * mid <= c)le = mid + 1,k = mid;
else r = mid - 1;
}
c=c-b * k;
}
for( ; !c.s[c.l] && c.l > 1; c.l--);
return c;
}
bigint operator += (bigint &b){return *this = *this + b;}
bigint operator += (LL &b){return *this = *this + b;}
bigint operator += (int &b){return *this = *this + b;}
bigint operator -= (bigint &b){return *this = *this - b;}
bigint operator -= (LL &b){return *this = *this - b;}
bigint operator -= (int &b){return *this = *this - b;}
bigint operator *= (bigint &b){return *this = *this * b;}
bigint operator *= (LL &b){return *this = *this * b;}
bigint operator *= (int &b){return *this = *this * b;}
bigint operator /= (bigint &b){return *this = *this / b;}
bigint operator /= (LL &b){return *this = *this / b;}
bigint operator /= (int &b){return *this = *this / b;}
bigint operator %= (bigint &b){return *this = *this % b;}
bigint operator %= (LL &b){return *this = *this % b;}
bigint operator %= (int &b){return *this = *this % b;}
bool operator < (const bigint &b) const {
if(l ^ b.l)return l < b.l;
for(int i = l; i; -- i)if (s[i] ^ b.s[i])return s[i] < b.s[i];
return false;
}
bool operator <= (const bigint &b) const {
if(l ^ b.l)return l < b.l;
for(int i = l; i; -- i)if (s[i] ^ b.s[i])return s[i] < b.s[i];
return true;
}
bool operator > (const bigint &b) const {
if(l ^ b.l)return l > b.l;
for(int i = l; i; -- i)
if (s[i] ^ b.s[i])return s[i] > b.s[i];
return false;
}
bool operator >= (const bigint &b) const {
if(l ^ b.l) return l > b.l;
for(int i = l; i; -- i) if (s[i] ^ b.s[i]) return s[i] > b.s[i];
return true;
}
bool operator == (const bigint &b) const {
if(l ^ b.l) return false;
for(int i = l; i; -- i) if (s[i] ^ b.s[i]) return false;
return true;
}
bool operator != (const bigint &b) const {
if(l ^ b.l) return true;
for(int i = l; i; -- i) if (s[i] ^ b.s[i]) return true;
return false;
}
bool operator < (LL b) const { bigint c; return *this < (c = b); }
bool operator <= (LL b) const { bigint c; return *this <= (c = b); }
bool operator > (LL b) const { bigint c; return *this > (c = b); }
bool operator >= (LL b) const { bigint c; return *this >= (c = b); }
bool operator == (LL b) const { bigint c; return *this == (c = b); }
bool operator != (LL b) const { bigint c; return *this != (c = b); }
bool operator < (int b) const { bigint c; return *this < (c = b); }
bool operator <= (int b) const { bigint c; return *this <= (c = b); }
bool operator > (int b) const { bigint c; return *this > (c = b); }
bool operator >= (int b) const { bigint c; return *this >= (c = b); }
bool operator == (int b) const { bigint c; return *this == (c = b); }
bool operator != (int b) const { bigint c; return *this != (c = b); }
} a, b;
int main() {
a.read(); b.read();
a.print(); printf("+"); b.print(); printf("="); (a + b).print(); puts("");
a.print(); printf("-"); b.print(); printf("=");
if(a < b) { putchar('-'); (b - a).print(); }
else (a - b).print(); puts("");
a.print(); printf("*"); b.print(); printf("="); (a * b).print(); puts("");
a.print(); printf("/"); b.print(); printf("="); (a / b).print(); puts("");
a.print(); printf("%%"); b.print(); printf("="); (a % b).print(); puts("");
if(a < b) printf("a<b
");
if(a <= b) printf("a<=b
");
if(a > b) printf("a>b
");
if(a >= b) printf("a>=b
");
if(a == b) printf("a==b
");
if(a != b) printf("a!=b
");
return 0;
}