高精度模板，留个备份：
1 #include <cstdio> 2 #include <cstring> 3 4 struct BigNumber 5 { 6 static const long long BASE = 1000000000; 7 static const int BASEDIGS = 9; 8 9 int ndigs; 10 long long *digs; 11 12 void init(int n, const long long *d) 13 { 14 while (n > 0 && d[n - 1] == 0) 15 --n; 16 ndigs = n; 17 digs = new long long[n]; 18 for (int i = 0; i < n; ++i) 19 digs[i] = d[i]; 20 } 21 22 BigNumber(int n, const long long *d) 23 { 24 init(n, d); 25 } 26 27 BigNumber operator <<(int sh) const 28 { 29 int n = sh + ndigs; 30 long long d[n]; 31 for (int i = 0; i < sh; ++i) 32 d[i] = 0; 33 for (int i = 0; i < ndigs; ++i) 34 d[i + sh] = digs[i]; 35 return BigNumber(n, d); 36 } 37 38 BigNumber(long long x = 0) 39 { 40 long long d[2]; 41 d[0] = x % BASE; 42 d[1] = x / BASE; 43 init(2, d); 44 } 45 46 BigNumber(const BigNumber&a) 47 { 48 init(a.ndigs, a.digs); 49 } 50 51 BigNumber(const char *s) 52 { 53 int n = strlen(s), nd = n / BASEDIGS + 1; 54 long long d[nd]; 55 for (int i = 0; i < nd; i++) 56 { 57 d[i] = 0; 58 for (int j = BASEDIGS - 1; j >= 0; j--) 59 { 60 long long poz = i * BASEDIGS + j; 61 if (poz < n) d[i] = 10 * d[i] + s[n - 1 - poz] - '0'; 62 } 63 } 64 init(nd, d); 65 } 66 67 ~BigNumber() 68 { 69 delete[] digs; 70 } 71 72 BigNumber &operator =(const BigNumber &a) 73 { 74 delete[] digs; 75 init(a.ndigs, a.digs); 76 return *this; 77 } 78 79 BigNumber operator +(const BigNumber &a) const 80 { 81 int n = (ndigs > a.ndigs ? ndigs : a.ndigs) + 1; 82 long long d[n]; 83 for (int i = 0; i < n; i++) 84 d[i] = 0; 85 for (int i = 0; i < n; i++) 86 { 87 if (i < ndigs) d[i] += digs[i]; 88 if (i < a.ndigs) d[i] += a.digs[i]; 89 if (d[i] >= BASE) 90 { 91 d[i] -= BASE; 92 ++d[i + 1]; 93 } 94 } 95 return BigNumber(n, d); 96 } 97 98 BigNumber &operator +=(const BigNumber &a) 99 { 100 return *this = *this + a; 101 } 102 103 BigNumber operator -(const BigNumber &a) const 104 { 105 long long d[ndigs]; 106 for (int i = 0; i < ndigs; i++) 107 d[i] = digs[i]; 108 for (int i = 0; i < ndigs; i++) 109 { 110 if (i < a.ndigs) d[i] -= a.digs[i]; 111 if (d[i] < 0) 112 { 113 d[i] += BASE; 114 --d[i + 1]; 115 } 116 } 117 return BigNumber(ndigs, d); 118 } 119 120 BigNumber &operator -=(const BigNumber &a) 121 { 122 return *this = *this - a; 123 } 124 125 BigNumber operator *(const BigNumber &a) const 126 { 127 int n = ndigs + a.ndigs; 128 long long d[n]; 129 for (int i = 0; i < n; i++) 130 d[i] = 0; 131 for (int i = 0; i < ndigs; i++) 132 { 133 long long p = 0; 134 for (int j = 0; j < a.ndigs; j++) 135 { 136 long long v = (long long) (digs[i]) * a.digs[j]; 137 long long v1 = v / BASE, v0 = v % BASE; 138 d[i + j] += v0 + p; 139 p = v1 + d[i + j] / BASE; 140 d[i + j] %= BASE; 141 } 142 for(int j = i + a.ndigs; p > 0; ++j) 143 { 144 d[j] += p; 145 p = d[j] / BASE; 146 d[j] %= BASE; 147 } 148 } 149 return BigNumber(n, d); 150 } 151 152 BigNumber &operator *=(const BigNumber &a) 153 { 154 return *this = *this * a; 155 } 156 157 BigNumber operator /(const BigNumber &a) const 158 { 159 int n = (ndigs - a.ndigs + 1 > 0 ? ndigs - a.ndigs + 1 : 0); 160 long long d[n]; 161 BigNumber prod; 162 for(int i = n - 1; i >= 0; i--) 163 { 164 long long l = 0, r = BASE - 1; 165 while(l < r) 166 { 167 long long m = (l + r + 1) / 2; 168 if (*this < prod + (a * m << i)) 169 r = m - 1; 170 else l = m; 171 } 172 prod += a * l << i; 173 d[i] = l; 174 } 175 return BigNumber(n, d); 176 } 177 178 BigNumber &operator /=(const BigNumber &a) 179 { 180 return *this = *this / a; 181 } 182 183 BigNumber operator %(const BigNumber &a) const 184 { 185 return *this - *this / a * a; 186 } 187 188 BigNumber &operator%=(const BigNumber&a) { 189 return *this = *this % a; 190 } 191 192 BigNumber sqrt() const 193 { 194 int n = (ndigs + 1) / 2; 195 long long d[n]; 196 for (int i = 0; i < n; i++) 197 d[i] = 0; 198 BigNumber sq; 199 for (int i = n - 1; i >= 0; i--) 200 { 201 BigNumber a(n, d); 202 long long l = 0, r = BASE - 1; 203 while (l < r) { 204 long long m = (l + r + 1) / 2; 205 if (*this < sq + (a * 2 * m << i) + (BigNumber(m) * m << 2 * i)) 206 r = m - 1; 207 else l = m; 208 } 209 sq += (a * 2 * l << i) + (BigNumber(l) * l << 2 * i); 210 d[i] = l; 211 } 212 return BigNumber(n, d); 213 } 214 215 BigNumber operator *(long long x) const 216 { 217 int n = ndigs + 1; 218 long long d[n]; 219 long long a = 0; 220 for (int i = 0; i < ndigs; i++) 221 { 222 a += digs[i] * x; 223 d[i] = a % BASE; 224 a /= BASE; 225 } 226 d[ndigs] = a; 227 return BigNumber(n, d); 228 } 229 230 BigNumber &operator *=(long long x) 231 { 232 return *this = *this * x; 233 } 234 235 BigNumber operator /(long long x) const 236 { 237 long long d[ndigs]; 238 long long a = 0; 239 for (int i = ndigs - 1; i >= 0; i--) 240 { 241 a = BASE * a + digs[i]; 242 d[i] = a / x; 243 a %= x; 244 } 245 return BigNumber(ndigs, d); 246 } 247 248 BigNumber &operator /=(long long x) 249 { 250 return *this = *this / x; 251 } 252 253 long long operator %(long long x) const 254 { 255 long long a = 0; 256 for (int i = ndigs - 1; i >= 0; i--) 257 { 258 a = BASE * a + digs[i]; 259 a %= x; 260 } 261 return a; 262 } 263 264 bool operator <(const BigNumber &a) const 265 { 266 if (ndigs < a.ndigs) return true; 267 if (ndigs > a.ndigs) return false; 268 for(int i = ndigs - 1; i >= 0; i--) 269 { 270 if (digs[i] < a.digs[i]) return true; 271 if (digs[i] > a.digs[i]) return false; 272 } 273 return false; 274 } 275 276 bool operator ==(const BigNumber &a) const 277 { 278 if (ndigs != a.ndigs) return false; 279 for (int i = 0; i < ndigs; i++) 280 { 281 if (digs[i] != a.digs[i]) 282 return false; 283 } 284 return true; 285 } 286 287 bool operator >(const BigNumber &a) const 288 { 289 return a < *this; 290 } 291 292 bool operator <=(const BigNumber &a) const 293 { 294 return !(a < *this); 295 } 296 297 bool operator >=(const BigNumber &a) const 298 { 299 return !(*this < a); 300 } 301 302 bool operator !=(const BigNumber &a) const 303 { 304 return !(*this == a); 305 } 306 307 void write() const 308 { 309 if (ndigs == 0) printf("0"); 310 else 311 { 312 printf("%lld", digs[ndigs - 1]); 313 for (int i = ndigs - 2; i >= 0; i--) 314 printf("%0*lld", BASEDIGS, digs[i]); 315 } 316 } 317 318 void write(char *buf) const 319 { 320 if(ndigs == 0) sprintf(buf, "0"); 321 else 322 { 323 long long pos = 0; 324 pos += sprintf(buf, "%lld", digs[ndigs - 1]); 325 for (int i = ndigs - 2; i >= 0; i--) 326 pos += sprintf(buf + pos, "%0*lld", BASEDIGS, digs[i]); 327 } 328 } 329 };