高精度加法
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int LEN = 200 + 1; int a[LEN], b[LEN], c[LEN]; char s1[LEN], s2[LEN]; int main() { scanf("%s%s", s1, s2); a[0] = strlen(s1), b[0] = strlen(s2); c[0] = max(a[0], b[0]) + 1; for(int i = 0; i < a[0]; i++) a[i + 1] = s1[a[0] - i - 1] - '0'; for(int i = 0; i < b[0]; i++) b[i + 1] = s2[b[0] - i - 1] - '0'; int x = 0; for(int i = 1; i <= c[0]; i++) { c[i] = a[i] + b[i] + x; x = c[i] / 10; c[i] %= 10; } while(c[c[0]] == 0 && c[0] > 1) c[0]--; for(int i = c[0]; i >= 1; i--) putchar(c[i] + '0'); }
高精度减法
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int LEN = 200 + 1; int a[LEN], b[LEN], c[LEN]; char s1[LEN], s2[LEN]; int main() { scanf("%s%s", s1, s2); a[0] = strlen(s1), b[0] = strlen(s2); c[0] = max(a[0], b[0]) + 1; for(int i = 0; i < a[0]; i++) a[i + 1] = s1[a[0] - i - 1] - '0'; for(int i = 0; i < b[0]; i++) b[i + 1] = s2[b[0] - i - 1] - '0'; for(int i = 1; i <= c[0]; i++) { c[i] = a[i] - b[i]; if(c[i] < 0) { c[i] += 10; a[i + 1]--; } } while(c[c[0]] == 0 && c[0] > 1) c[0]--; for(int i = c[0]; i >= 1; i--) putchar(c[i] + '0'); }
高精度乘法
高精度乘单精度
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int LEN = 200 + 1; int b, lenb, a[LEN], c[LEN << 1]; char s[LEN]; int Digit_num(int x) { int ret = 0; while(x) { x /= 10; ret++; } return ret; } int main() { scanf("%s%d", s, &b); a[0] = strlen(s), lenb = Digit_num(b); c[0] = a[0] + lenb; for(int i = 0; i < a[0]; i++) a[i + 1] = s[a[0] - i - 1] - '0'; int x = 0; for(int i = 1; i <= c[0]; i++) { c[i] = a[i] * b + x; x = c[i] / 10; c[i] %= 10; } while(x) { c[c[0]++] = x % 10; x /= 10; } while(c[c[0]] == 0 && c[0] > 1) c[0]--; for(int i = c[0]; i >= 1; i--) putchar(c[i] + '0'); }
高精度乘高精度
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int LEN = 200 + 1; int a[LEN], b[LEN], c[LEN << 1]; char s1[LEN], s2[LEN]; int main() { scanf("%s%s", s1, s2); a[0] = strlen(s1), b[0] = strlen(s2); c[0] = a[0] + b[0]; for(int i = 0; i < a[0]; i++) a[i + 1] = s1[a[0] - i - 1] - '0'; for(int i = 0; i < b[0]; i++) b[i + 1] = s2[b[0] - i - 1] - '0'; for(int i = 1; i <= a[0]; i++) { int x = 0; for(int j = 1; j <= b[0]; j++) { c[i + j - 1] += a[i] * b[j] + x; x = c[i + j - 1] / 10; c[i + j - 1] %= 10; } c[i + b[0]] = x; } while(c[c[0]] > 0) c[0]++; while(c[c[0]] == 0 && c[0] > 1) c[0]--; for(int i = c[0]; i >= 1; i--) putchar(c[i] + '0'); }
高精度除法
高精度除以单精度
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int LEN = 200 + 1; int a[LEN], c[LEN], b; char s[LEN]; int main() { scanf("%s%d", s, &b); a[0] = strlen(s); for(int i = 0; i < a[0]; i++) a[i + 1] = s[i] - '0'; int x = 0; for(int i = 1; i <= a[0]; i++) { x = x * 10 + a[i]; c[++c[0]] = x / b; x %= b; } int start = 1; while(c[start] == 0 && start < c[0]) start++; for(int i = start; i <= c[0]; i++) putchar(c[i] + '0'); printf(" mod: %d", x); }
高精度除以高精度
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int LEN = 100 + 1; int a[LEN], b[LEN], c[LEN], tmp[LEN]; char s1[LEN], s2[LEN]; void Sub(int a[], int b[]) { for(int i = 1; i <= a[0]; i++) { a[i] = a[i] - b[i]; if(a[i] < 0) { a[i] += 10; a[i + 1]--; } } while(a[a[0]] == 0 && a[0] > 1) a[0]--; } int Comp(int a[], int b[]) { int up = max(a[0], b[0]); for(int i = a[0] + 1; i <= up; i++) a[i] = 0; for(int i = b[0] + 1; i <= up; i++) b[i] = 0; for(int i = 0; i < up; i++) { if(a[up - i] > b[up - i]) return 1; if(a[up - i] < b[up - i]) return -1; } return 0; } void Joint(int p[], int q[], int det) { for(int i = 1; i <= p[0]; i++) q[i + det - 1] = p[i]; q[0] = p[0] + det - 1; } int main() { scanf("%s%s", s1, s2); a[0] = strlen(s1), b[0] = strlen(s2); c[0] = a[0] - b[0] + 1; for(int i = 0; i < a[0]; i++) a[i + 1] = s1[a[0] - i - 1] - '0'; for(int i = 0; i < b[0]; i++) b[i + 1] = s2[b[0] - i - 1] - '0'; for(int i = c[0]; i >= 1; i--) { memset(tmp, 0, sizeof(tmp)); Joint(b, tmp, i); while(Comp(a, tmp) >= 0) { Sub(a, tmp); c[i]++; } } while(c[c[0]] == 0 && c[0] > 1) c[0]--; if(c[0] < 1) c[c[0] = 1] = 0; for(int i = c[0]; i >= 1; i--) printf("%d", c[i]); }
高精度四则运算BIGNUM型
写了两节课QwQ
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 6 const int LEN = 10000 + 1; 7 8 //支持任意两个非负整数的加、减、乘、除、取模运算 9 struct BIGNUM { 10 int s[LEN << 1]; 11 bool flag; 12 BIGNUM() { 13 memset(s, 0, sizeof(s)); 14 flag = s[0] = 1; 15 } 16 void init() { 17 memset(s, 0, sizeof(s)); 18 s[0] = 1; 19 } 20 21 BIGNUM operator = (const char *num) { 22 s[0] = strlen(num); 23 for(int i = 0; i < s[0]; i++) s[i + 1] = num[s[0] - i - 1] - '0'; 24 return *this; 25 } 26 BIGNUM operator = (const int num) { 27 char a[LEN]; 28 sprintf(a, "%d", num); 29 *this = a; 30 return *this; 31 } 32 BIGNUM(int num) { *this = num; } 33 BIGNUM(const char *num) { *this = num; } 34 BIGNUM operator = (const BIGNUM &num) { 35 int l = max(s[0], num.s[0]); 36 for(int i = 0; i <= l; i++) s[i] = num.s[i]; 37 } 38 39 40 BIGNUM operator + (const BIGNUM &a) { 41 BIGNUM c; 42 int x = 0; 43 c.s[0] = max(a.s[0], s[0]) + 1; 44 for(int i = 1; i <= c.s[0]; i++) { 45 c.s[i] = a.s[i] + s[i] + x; 46 x = c.s[i] / 10; 47 c.s[i] %= 10; 48 } 49 while(c.s[c.s[0]] == 0 && c.s[0] > 1) c.s[0]--; 50 return c; 51 } 52 BIGNUM operator += (const BIGNUM &a) { 53 *this = *this + a; 54 return *this; 55 } 56 57 bool operator == (const BIGNUM &a) { 58 int up = max(s[0], a.s[0]); 59 for(int i = 0; i < up; i++) 60 if(s[up - i] != a.s[up - i]) return false; 61 return true; 62 } 63 bool operator > (const BIGNUM &a) { 64 if(s[0] != a.s[0]) return s[0] > a.s[0]; 65 int up = max(s[0], a.s[0]); 66 for(int i = 0; i < up; i++) 67 if(s[up - i] != a.s[up - i]) return s[up - i] > a.s[up - i]; 68 return false; 69 } 70 bool operator < (const BIGNUM &a) { 71 if(s[0] != a.s[0]) return s[0] < a.s[0]; 72 int up = max(s[0], a.s[0]); 73 for(int i = 0; i < up; i++) 74 if(s[up - i] != a.s[up - i]) return s[up - i] < a.s[up - i]; 75 return false; 76 } 77 bool operator >= (const BIGNUM &a) { 78 if(*this > a || *this == a) return true; 79 return false; 80 } 81 bool operator <= (const BIGNUM &a) { 82 if(*this < a || *this == a) return true; 83 return false; 84 } 85 86 BIGNUM operator - (const BIGNUM &a) { 87 BIGNUM c; 88 c.s[0] = max(a.s[0], s[0]) + 1; 89 if(*this < a) c.flag = false; 90 for(int i = 1; i <= c.s[0]; i++) { 91 if(c.flag) c.s[i] += s[i] - a.s[i]; 92 else c.s[i] += a.s[i] - s[i]; 93 if(c.s[i] < 0) { 94 c.s[i] += 10; 95 c.s[i + 1]--; 96 } 97 } 98 while(c.s[c.s[0]] == 0 && c.s[0] > 1) c.s[0]--; 99 return c; 100 } 101 BIGNUM operator -= (const BIGNUM &a) { 102 *this = *this - a; 103 return *this; 104 } 105 BIGNUM operator * (const BIGNUM &a) { 106 BIGNUM c; 107 c.s[0] = s[0] + a.s[0]; 108 for(int i = 1; i <= s[0]; i++) { 109 int x = 0; 110 for(int j = 1; j <= a.s[0]; j++) { 111 c.s[i + j - 1] += s[i] * a.s[j] + x; 112 x = c.s[i + j - 1] / 10; 113 c.s[i + j - 1] %= 10; 114 } 115 c.s[i + a.s[0]] = x; 116 } 117 while(c.s[c.s[0]] > 0) c.s[0]++; 118 while(c.s[c.s[0]] == 0 && c.s[0] > 1) c.s[0]--; 119 return c; 120 } 121 BIGNUM operator *= (const BIGNUM &a) { 122 *this = *this * a; 123 return *this; 124 } 125 126 127 128 BIGNUM operator / (const BIGNUM &a) { 129 BIGNUM c, tmp; 130 c.s[0] = s[0] - a.s[0] + 1; 131 for(int i = c.s[0]; i >= 1; i--) { 132 tmp.init(); 133 for(int j = 1; j <= a.s[0]; j++) tmp.s[i + j - 1] = a.s[j]; 134 tmp.s[0] = a.s[0] + i - 1; 135 while(*this >= tmp) { 136 *this = *this - tmp; 137 c.s[i]++; 138 } 139 } 140 while(c.s[c.s[0]] == 0 && c.s[0] > 1) c.s[0]--; 141 if(c.s[0] < 1) c.s[c.s[0] = 1] = 0; 142 return c; 143 } 144 BIGNUM operator /= (const BIGNUM &a) { 145 *this = *this / a; 146 return *this; 147 } 148 BIGNUM operator % (const BIGNUM &a) { 149 BIGNUM d = *this, c = *this / a; 150 c *= a; 151 return d - c; 152 } 153 BIGNUM operator %= (const BIGNUM &a) { 154 *this = *this % a; 155 return *this; 156 } 157 }; 158 ostream& operator << (ostream &out, const BIGNUM &a) { 159 if(!a.flag) putchar('-'); 160 for(int i = a.s[0]; i >= 1; i--) 161 cout << a.s[i]; 162 return out; 163 } 164 istream& operator >> (istream &in, BIGNUM &a) { 165 char str[LEN]; 166 in >> str; 167 a = str; 168 return in; 169 } 170 171 BIGNUM a, b; 172 int main() { 173 cin >> a >> b; 174 cout << a + b << endl; 175 cout << a - b << endl; 176 cout << a * b << endl; 177 cout << a / b << endl; 178 cout << a % b << endl; 179 }
压位高精度：
加法
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int LEN = 200 + 1; const int BIT = 8; const int MOD = 100000000;//1eBIT int a[LEN/BIT], b[LEN/BIT], c[LEN/BIT]; char s1[LEN], s2[LEN]; int main() { scanf("%s%s", s1, s2); int la = strlen(s1), lb = strlen(s2); for(int i = la - 1; i >= 0; i -= BIT) { ++a[0]; long long w = 1; for(int j = i; j > i - BIT && j >= 0; j--) { a[a[0]] += (s1[j] ^ 48) * w; w = (w << 1) + (w << 3); } } for(int i = lb - 1; i >= 0; i -= BIT) { ++b[0]; long long w = 1; for(int j = i; j > i - BIT && j >= 0; j--) { b[b[0]] += (s2[j] ^ 48) * w; w = (w << 1) + (w << 3); } } int x = 0; c[0] = max(a[0], b[0]); for(int i = 1; i <= c[0]; i++) { c[i] = a[i] + b[i] + x; x = c[i] / MOD; c[i] %= MOD; } c[++c[0]] = x; while(c[c[0]] == 0 && c[0] > 1) c[0]--; printf("%d", c[c[0]]); for(int i = c[0] - 1; i >= 1; i--) printf("%08d", c[i]); }
减法
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int LEN = 200 + 1; const int BIT = 8; const int MOD = 100000000;//1eBIT int a[LEN/BIT], b[LEN/BIT], c[LEN/BIT]; char s1[LEN], s2[LEN]; int main() { scanf("%s%s", s1, s2); int la = strlen(s1), lb = strlen(s2); for(int i = la - 1; i >= 0; i -= BIT) { ++a[0]; long long w = 1; for(int j = i; j > i - BIT && j >= 0; j--) { a[a[0]] += (s1[j] ^ 48) * w; w = (w << 1) + (w << 3); } } for(int i = lb - 1; i >= 0; i -= BIT) { ++b[0]; long long w = 1; for(int j = i; j > i - BIT && j >= 0; j--) { b[b[0]] += (s2[j] ^ 48) * w; w = (w << 1) + (w << 3); } } c[0] = max(a[0], b[0]); for(int i = 1; i <= c[0]; i++) { c[i] += a[i] - b[i]; if(c[i] < 0) { c[i] += MOD; c[i + 1]--; } } while(c[c[0]] == 0 && c[0] > 1) c[0]--; printf("%d", c[c[0]]); for(int i = c[0] - 1; i >= 1; i--) printf("%08d", c[i]); }
乘法
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int LEN = 2000 + 1; const int BIT = 8; const int MOD = 100000000;//1eBIT long long a[LEN/BIT], b[LEN/BIT], c[(LEN<<1)/BIT]; char s1[LEN], s2[LEN]; int main() { scanf("%s%s", s1, s2); int la = strlen(s1), lb = strlen(s2); for(int i = la - 1; i >= 0; i -= BIT) { ++a[0]; long long w = 1; for(int j = i; j > i - BIT && j >= 0; j--) { a[a[0]] += (s1[j] ^ 48) * w; w = (w << 1) + (w << 3); } } for(int i = lb - 1; i >= 0; i -= BIT) { ++b[0]; long long w = 1; for(int j = i; j > i - BIT && j >= 0; j--) { b[b[0]] += (s2[j]^48) * w; w = (w << 1) + (w << 3); } } c[0] = a[0] + b[0]; for(int i = 1; i <= a[0]; i++) { long long x = 0; for(int j = 1; j <= b[0]; j++) { c[i + j - 1] += a[i] * b[j] + x; x = c[i + j - 1] / MOD; c[i + j - 1] %= MOD; } c[i + b[0]] = x; } while(c[c[0] + 1] > 0) c[0]++; while(c[c[0]] == 0 && c[0] > 1) c[0]--; printf("%d", c[c[0]]); for(int i = c[0] - 1; i >= 1; i--) printf("%08d", c[i]); }
除法（模拟减法，倍增优化）
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int LEN = 5000 + 10; const int BIT = 8; const int MOD = 100000000;//1eBIT int a[LEN/BIT], b[LEN/BIT], c[LEN/BIT], tmp[LEN/BIT], lt[LEN/BIT]; char s1[LEN], s2[LEN]; void Plus(int a[], int b[]) { int x = 0; a[0] = max(a[0], b[0]); for(int i = 1; i <= a[0]; i++) { a[i] = a[i] + b[i] + x; x = a[i] / MOD; a[i] %= MOD; } a[++a[0]] = x; while(a[a[0]] == 0 && a[0] > 1) a[0]--; } void Sub(int a[], int b[]) { for(int i = 1; i <= a[0]; i++) { a[i] = a[i] - b[i]; if(a[i] < 0) { a[i] += MOD; a[i + 1]--; } } while(a[a[0]] == 0 && a[0] > 1) a[0]--; } int Comp(int a[], int b[]) { int up = max(a[0], b[0]); for(int i = a[0] + 1; i <= up; i++) a[i] = 0; for(int i = b[0] + 1; i <= up; i++) b[i] = 0; for(int i = 0; i < up; i++) { if(a[up - i] > b[up - i]) return 1; if(a[up - i] < b[up - i]) return -1; } return 0; } void Joint(int p[], int q[]) { for(int i = p[0]; i > q[0]; i--) p[i] = 0; for(int i = 0; i <= q[0]; i++) p[i] = q[i]; } void Left_move(int num[]) { ++num[0]; for(int i = 1; i <= num[0]; i++) { num[i] <<= 1; if(num[i - 1] >= MOD) num[i - 1] -= MOD, ++num[i]; } while(num[num[0]] == 0 && num[0] > 1) num[0]--; } void Right_move(int num[]) { for(int i = num[0]; i >= 1; i--) { if((num[i] & 1) && i > 1) num[i - 1] += MOD; num[i] >>= 1; } while(num[num[0]] == 0 && num[0] > 1) num[0]--; } int main() { scanf("%s%s", s1, s2); int la = strlen(s1), lb = strlen(s2); for(int i = la - 1; i >= 0; i -= BIT) { ++a[0]; long long w = 1; for(int j = i; j > i - BIT && j >= 0; j--) { a[a[0]] += (s1[j] ^ 48) * w; w = (w << 1) + (w << 3); } } for(int i = lb - 1; i >= 0; i -= BIT) { ++b[0]; long long w = 1; for(int j = i; j > i - BIT && j >= 0; j--) { b[b[0]] += (s2[j] ^ 48) * w; w = (w << 1) + (w << 3); } } tmp[1] = 1; while(Comp(a, b) >= 0) { Left_move(b), Left_move(tmp); } while(tmp[0] > 1 || tmp[1]) { if(Comp(a, b) >= 0) { Sub(a, b); Plus(lt, tmp); } Right_move(b), Right_move(tmp); } Joint(c, lt); Joint(lt, a); while(c[c[0]] == 0 && c[0] > 1) c[0]--; if(c[0] < 1) c[c[0] = 1] = 0; printf("%d", c[c[0]]); for(int i = c[0] - 1; i >= 1; i--) printf("%08d", c[i]); }
大整数型压位高精度：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 6 const int LEN = 10000 + 1; 7 8 //支持加、减、乘、除、取模等非负整数之间的运算 9 //可调整压位位数，除法使用倍增优化 10 struct BIGNUM { 11 static const int BIT = 8; 12 static const int MOD = 100000000;//1eBIT 13 14 long long s[LEN]; 15 bool flag; 16 BIGNUM() { 17 memset(s, 0, sizeof(s)); 18 flag = s[0] = 1; 19 } 20 void init() { 21 memset(s, 0, sizeof(s)); 22 s[0] = 1; 23 } 24 25 BIGNUM operator = (const char *num) { 26 int l = strlen(num); 27 s[0] = 0; 28 for(int i = l - 1; i >= 0; i -= BIT) { 29 ++s[0]; 30 long long w = 1; 31 for(int j = i; j > i - BIT && j >= 0; j--) { 32 s[s[0]] += (num[j] ^ 48) * w; 33 w = (w << 1) + (w << 3); 34 } 35 } 36 return *this; 37 } 38 BIGNUM operator = (const int num) { 39 char a[LEN]; 40 sprintf(a, "%d", num); 41 *this = a; 42 return *this; 43 } 44 BIGNUM(int num) { *this = num; } 45 BIGNUM(const char *num) { *this = num; } 46 47 BIGNUM operator + (const BIGNUM &a) { 48 BIGNUM c; 49 int x = 0; 50 c.s[0] = max(a.s[0], s[0]) + 1; 51 for(int i = 1; i <= c.s[0]; i++) { 52 c.s[i] = a.s[i] + s[i] + x; 53 x = c.s[i] / MOD; 54 c.s[i] %= MOD; 55 } 56 while(c.s[c.s[0]] == 0 && c.s[0] > 1) c.s[0]--; 57 return c; 58 } 59 BIGNUM operator += (const BIGNUM &a) { 60 *this = *this + a; 61 return *this; 62 } 63 64 bool operator == (const BIGNUM &a) { 65 int up = max(s[0], a.s[0]); 66 for(int i = 0; i < up; i++) 67 if(s[up - i] != a.s[up - i]) return false; 68 return true; 69 } 70 bool operator > (const BIGNUM &a) { 71 if(s[0] != a.s[0]) return s[0] > a.s[0]; 72 int up = max(s[0], a.s[0]); 73 for(int i = 0; i < up; i++) 74 if(s[up - i] != a.s[up - i]) return s[up - i] > a.s[up - i]; 75 return false; 76 } 77 bool operator < (const BIGNUM &a) { 78 if(s[0] != a.s[0]) return s[0] < a.s[0]; 79 int up = max(s[0], a.s[0]); 80 for(int i = 0; i < up; i++) 81 if(s[up - i] != a.s[up - i]) return s[up - i] < a.s[up - i]; 82 return false; 83 } 84 bool operator >= (const BIGNUM &a) { 85 if(*this > a || *this == a) return true; 86 return false; 87 } 88 bool operator <= (const BIGNUM &a) { 89 if(*this < a || *this == a) return true; 90 return false; 91 } 92 93 BIGNUM operator - (const BIGNUM &a) { 94 BIGNUM c; 95 c.s[0] = max(a.s[0], s[0]) + 1; 96 if(*this < a) c.flag = false; 97 for(int i = 1; i <= c.s[0]; i++) { 98 if(c.flag) c.s[i] += s[i] - a.s[i]; 99 else c.s[i] += a.s[i] - s[i]; 100 if(c.s[i] < 0) { 101 c.s[i] += MOD; 102 c.s[i + 1]--; 103 } 104 } 105 while(c.s[c.s[0]] == 0 && c.s[0] > 1) c.s[0]--; 106 return c; 107 } 108 BIGNUM operator -= (const BIGNUM &a) { 109 *this = *this - a; 110 return *this; 111 } 112 BIGNUM operator * (const BIGNUM &a) { 113 BIGNUM c; 114 c.s[0] = s[0] + a.s[0]; 115 for(int i = 1; i <= s[0]; i++) { 116 int x = 0; 117 for(int j = 1; j <= a.s[0]; j++) { 118 c.s[i + j - 1] += s[i] * a.s[j] + x; 119 x = c.s[i + j - 1] / MOD; 120 c.s[i + j - 1] %= MOD; 121 } 122 c.s[i + a.s[0]] = x; 123 } 124 while(c.s[c.s[0]] > 0) c.s[0]++; 125 while(c.s[c.s[0]] == 0 && c.s[0] > 1) c.s[0]--; 126 return c; 127 } 128 BIGNUM operator *= (const BIGNUM &a) { 129 *this = *this * a; 130 return *this; 131 } 132 133 BIGNUM operator << (const int &num) { 134 s[0]++; 135 for(int i = 1; i <= s[0]; i++) { 136 s[i] <<= num; 137 if(s[i - 1] >= MOD) 138 s[i - 1] -= MOD, ++s[i]; 139 } 140 while(s[s[0]] == 0 && s[0] > 1) s[0]--; 141 return *this; 142 } 143 BIGNUM operator >> (const int &num) { 144 for(int i = s[0]; i >= 1; i--) { 145 if((s[i] & 1) && i > 1) s[i - 1] += MOD; 146 s[i] >>= num; 147 } 148 while(s[s[0]] == 0 && s[0] > 1) s[0]--; 149 return *this; 150 } 151 152 BIGNUM operator / (const BIGNUM &k) { 153 BIGNUM c = *this, tmp, lt, a; 154 a = k; 155 tmp.s[1] = 1; 156 while(c >= a) { 157 a = a << 1; 158 tmp = tmp << 1; 159 } 160 while(tmp.s[0] > 1 || tmp.s[1]) { 161 if(c >= a) { 162 c -= a; 163 lt += tmp; 164 } 165 a = a >> 1; 166 tmp = tmp >> 1; 167 } 168 c = lt; 169 while(c.s[c.s[0]] == 0 && c.s[0] > 1) c.s[0]--; 170 if(c.s[0] < 1) c.s[c.s[0] = 1] = 0; 171 return c; 172 } 173 BIGNUM operator /= (const BIGNUM &a) { 174 *this = *this / a; 175 return *this; 176 } 177 BIGNUM operator % (const BIGNUM &a) { 178 BIGNUM d = *this, c = *this / a; 179 c *= a; 180 return d - c; 181 } 182 BIGNUM operator %= (const BIGNUM &a) { 183 *this = *this % a; 184 return *this; 185 } 186 }; 187 ostream& operator << (ostream &out, const BIGNUM &a) { 188 if(!a.flag) putchar('-'); 189 printf("%d", a.s[a.s[0]]); 190 for(int i = a.s[0] - 1; i >= 1; i--) 191 printf("%08d", a.s[i]); 192 return out; 193 } 194 istream& operator >> (istream &in, BIGNUM &a) { 195 char str[LEN]; 196 in >> str; 197 a = str; 198 return in; 199 } 200 201 BIGNUM a, b; 202 int main() { 203 cin >> a >> b; 204 cout << a + b << endl; 205 cout << a - b << endl; 206 cout << a * b << endl; 207 cout << a / b << endl; 208 cout << a % b << endl; 209 }
也可以把压位压到9位..
时空复杂度都更优
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 6 const int LEN = 10000 + 1; 7 8 struct BIGNUM { 9 static const int BIT = 9; 10 static const int MOD = 1000000000;//1eBIT 11 12 long long s[LEN]; 13 bool flag; 14 BIGNUM() { 15 memset(s, 0, sizeof(s)); 16 flag = s[0] = 1; 17 } 18 void init() { 19 memset(s, 0, sizeof(s)); 20 s[0] = 1; 21 } 22 23 BIGNUM operator = (const char *num) { 24 int l = strlen(num); 25 s[0] = 0; 26 for(int i = l - 1; i >= 0; i -= BIT) { 27 ++s[0]; 28 long long w = 1; 29 for(int j = i; j > i - BIT && j >= 0; j--) { 30 s[s[0]] += (num[j] ^ 48) * w; 31 w = (w << 1) + (w << 3); 32 } 33 } 34 return *this; 35 } 36 BIGNUM operator = (const int num) { 37 char a[LEN]; 38 sprintf(a, "%d", num); 39 *this = a; 40 return *this; 41 } 42 BIGNUM(int num) { *this = num; } 43 BIGNUM(const char *num) { *this = num; } 44 45 BIGNUM operator + (const BIGNUM &a) { 46 BIGNUM c; 47 int x = 0; 48 c.s[0] = max(a.s[0], s[0]) + 1; 49 for(int i = 1; i <= c.s[0]; i++) { 50 c.s[i] = a.s[i] + s[i] + x; 51 x = c.s[i] / MOD; 52 c.s[i] %= MOD; 53 } 54 while(c.s[c.s[0]] == 0 && c.s[0] > 1) c.s[0]--; 55 return c; 56 } 57 BIGNUM operator += (const BIGNUM &a) { 58 *this = *this + a; 59 return *this; 60 } 61 62 bool operator == (const BIGNUM &a) { 63 int up = max(s[0], a.s[0]); 64 for(int i = 0; i < up; i++) 65 if(s[up - i] != a.s[up - i]) return false; 66 return true; 67 } 68 bool operator > (const BIGNUM &a) { 69 if(s[0] != a.s[0]) return s[0] > a.s[0]; 70 int up = max(s[0], a.s[0]); 71 for(int i = 0; i < up; i++) 72 if(s[up - i] != a.s[up - i]) return s[up - i] > a.s[up - i]; 73 return false; 74 } 75 bool operator < (const BIGNUM &a) { 76 if(s[0] != a.s[0]) return s[0] < a.s[0]; 77 int up = max(s[0], a.s[0]); 78 for(int i = 0; i < up; i++) 79 if(s[up - i] != a.s[up - i]) return s[up - i] < a.s[up - i]; 80 return false; 81 } 82 bool operator >= (const BIGNUM &a) { 83 if(*this > a || *this == a) return true; 84 return false; 85 } 86 bool operator <= (const BIGNUM &a) { 87 if(*this < a || *this == a) return true; 88 return false; 89 } 90 91 BIGNUM operator - (const BIGNUM &a) { 92 BIGNUM c; 93 c.s[0] = max(a.s[0], s[0]) + 1; 94 if(*this < a) c.flag = false; 95 for(int i = 1; i <= c.s[0]; i++) { 96 if(c.flag) c.s[i] += s[i] - a.s[i]; 97 else c.s[i] += a.s[i] - s[i]; 98 if(c.s[i] < 0) { 99 c.s[i] += MOD; 100 c.s[i + 1]--; 101 } 102 } 103 while(c.s[c.s[0]] == 0 && c.s[0] > 1) c.s[0]--; 104 return c; 105 } 106 BIGNUM operator -= (const BIGNUM &a) { 107 *this = *this - a; 108 return *this; 109 } 110 BIGNUM operator * (const BIGNUM &a) { 111 BIGNUM c; 112 c.s[0] = s[0] + a.s[0]; 113 for(int i = 1; i <= s[0]; i++) { 114 int x = 0; 115 for(int j = 1; j <= a.s[0]; j++) { 116 c.s[i + j - 1] += s[i] * a.s[j] + x; 117 x = c.s[i + j - 1] / MOD; 118 c.s[i + j - 1] %= MOD; 119 } 120 c.s[i + a.s[0]] = x; 121 } 122 while(c.s[c.s[0]] > 0) c.s[0]++; 123 while(c.s[c.s[0]] == 0 && c.s[0] > 1) c.s[0]--; 124 return c; 125 } 126 BIGNUM operator *= (const BIGNUM &a) { 127 *this = *this * a; 128 return *this; 129 } 130 131 BIGNUM operator << (const int &num) { 132 s[0]++; 133 for(int i = 1; i <= s[0]; i++) { 134 s[i] <<= num; 135 if(s[i - 1] >= MOD) 136 s[i - 1] -= MOD, ++s[i]; 137 } 138 while(s[s[0]] == 0 && s[0] > 1) s[0]--; 139 return *this; 140 } 141 BIGNUM operator >> (const int &num) { 142 for(int i = s[0]; i >= 1; i--) { 143 if((s[i] & 1) && i > 1) s[i - 1] += MOD; 144 s[i] >>= num; 145 } 146 while(s[s[0]] == 0 && s[0] > 1) s[0]--; 147 return *this; 148 } 149 150 BIGNUM operator / (const BIGNUM &k) { 151 BIGNUM c = *this, tmp, lt, a; 152 a = k; 153 tmp.s[1] = 1; 154 while(c >= a) { 155 a = a << 1; 156 tmp = tmp << 1; 157 } 158 while(tmp.s[0] > 1 || tmp.s[1]) { 159 if(c >= a) { 160 c -= a; 161 lt += tmp; 162 } 163 a = a >> 1; 164 tmp = tmp >> 1; 165 } 166 c = lt; 167 while(c.s[c.s[0]] == 0 && c.s[0] > 1) c.s[0]--; 168 if(c.s[0] < 1) c.s[c.s[0] = 1] = 0; 169 return c; 170 } 171 BIGNUM operator /= (const BIGNUM &a) { 172 *this = *this / a; 173 return *this; 174 } 175 BIGNUM operator % (const BIGNUM &a) { 176 BIGNUM d = *this, c = *this / a; 177 c *= a; 178 return d - c; 179 } 180 BIGNUM operator %= (const BIGNUM &a) { 181 *this = *this % a; 182 return *this; 183 } 184 }; 185 ostream& operator << (ostream &out, const BIGNUM &a) { 186 if(!a.flag) putchar('-'); 187 printf("%d", a.s[a.s[0]]); 188 for(int i = a.s[0] - 1; i >= 1; i--) 189 printf("%09d", a.s[i]); 190 return out; 191 } 192 istream& operator >> (istream &in, BIGNUM &a) { 193 char str[LEN]; 194 in >> str; 195 a = str; 196 return in; 197 } 198 199 BIGNUM a, b; 200 int main() { 201 cin >> a >> b; 202 cout << a + b << endl; 203 cout << a - b << endl; 204 cout << a * b << endl; 205 cout << a / b << endl; 206 cout << a % b << endl; 207 }