39 static uint64_t
const MSB = uint64_t(1) << 63;
48 explicit BigNumber(uint64_t* array)
52 void setArray(uint64_t* array) {
57 uint64_t
const* p = array;
64 size_t store(BigNumber
const& o) {
65 if (o.array == 0)
return store(0);
68 uint64_t
const* q = o.array;
71 if (*q != 0)
throw std::runtime_error(
72 "Non-zero assignment to null BigNumber");
83 size_t store(uint64_t n) {
87 if (n != 0)
throw std::runtime_error(
88 "Non-zero assignment to null BigNumber");
101 bool operator==(BigNumber
const& o)
const {
102 if (array == 0)
return o.operator==(0);
103 if (o.array == 0)
return operator==(0);
106 uint64_t
const* q = o.array;
108 if (*p++ != *q)
return false;
109 }
while (*q++ & MSB);
113 bool operator!=(BigNumber
const& o)
const {
114 return !operator==(o);
117 bool operator==(uint64_t n)
const {
118 return (array == 0) ? n == 0 :
119 array[0] == n && ((n & MSB) == 0 || array[1] == 1);
122 bool operator!=(uint64_t
const& o)
const {
123 return !operator==(o);
126 size_t add(BigNumber
const& o) {
128 uint64_t
const* q = o.array;
135 if ((*p & MSB) == 0) {
136 while ((*q & MSB) != 0) {
146 if ((*q & MSB) == 0) {
147 while ((*p & MSB) != 0) {
162 if (x & MSB) *p++ = 1;
167 uint32_t divide(uint32_t n) {
169 if (p == 0)
return 0;
178 uint64_t q = cont ? MSB : 0;
179 r = (r << 31) | ((*p & ~MSB) >> 32);
180 lldiv_t d = lldiv(r, 10LL);
182 r = (d.rem << 32) | (*p & ((uint64_t(1) << 32) - 1));
187 if (q != 0) cont =
true;
188 }
while (p != array);
193 size_t shiftLeft(
int k) {
197 for (uint64_t* q = array + size() - 1; q >= array; --q) {
200 for (uint64_t* q = array; q < array + w; ++q) {
210 uint64_t tmp = x | (*p << k);
211 x = (*p & ~MSB) >> (63 - k);
212 if (x == 0 && (*p & MSB) == 0) {
216 else if ((*p & MSB) == 0) {
228 T translate()
const {
229 uint64_t
const* p = array;
242 void printHelper(std::ostream& os) {
243 uint32_t r = divide(10);
244 if (*
this != 0) printHelper(os);
249 friend std::ostream& operator<<(std::ostream& os, BigNumber
const& o) {
250 uint64_t* storage =
new uint64_t[o.size()];
251 BigNumber n(storage);
258 operator std::string()
const {
259 std::ostringstream ss;
266 class FixedBigNumber {
271 for (
int i = 0; i < size; ++i) {
276 FixedBigNumber(uint32_t i) {
278 for (
int i = 1; i < size; ++i) {
283 FixedBigNumber& operator=(uint32_t n) {
285 for (
int i = 1; i < size; ++i) {
291 bool operator==(FixedBigNumber
const& o)
const {
292 for (
int i = 0; i < size; ++i) {
293 if (val[i] != o.val[i])
return false;
298 bool operator!=(FixedBigNumber
const& o)
const {
299 return !operator==(o);
302 bool operator==(uint32_t n)
const {
303 if (val[0] != n)
return false;
304 for (
int i = 1; i < size; ++i) {
305 if (val[i] != 0)
return false;
310 bool operator!=(uint32_t n)
const {
311 return !operator==(n);
314 void operator+=(FixedBigNumber
const& o) {
316 for (
int i = 0; i < size; ++i) {
322 if (x != 0)
throw std::runtime_error(
"FixedBigNumber overflow!");
325 FixedBigNumber operator+(FixedBigNumber
const& o)
const {
326 FixedBigNumber n = *
this;
331 uint32_t divide(uint32_t n) {
333 for (
int i = size - 1; i >= 0; --i) {
334 r = (r << 32) + val[i];
335 lldiv_t d = lldiv(r, n);
343 T translate()
const {
345 for (
int i = size - 1; i >= 0; --i) {
353 void printHelper(std::ostream& os) {
354 uint32_t r = divide(10);
355 if (*
this != 0) printHelper(os);
360 friend std::ostream& operator<<(std::ostream& os, FixedBigNumber
const& o) {
361 FixedBigNumber n = o;
366 operator std::string()
const {
367 std::ostringstream ss;