Advertisement
Dim_ov

Untitled

Dec 23rd, 2017
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.21 KB | None | 0 0
  1. struct bigint {
  2.     static const int base = 100000000;
  3.     static const int base_digits = 8;
  4.  
  5.     int z[30];
  6.     int zs;
  7.  
  8.     bigint(): zs(0) {}
  9.  
  10.     bigint(long long v) {
  11.         *this = v;
  12.     }
  13.  
  14.     bigint& operator=(long long v) {
  15.         zs = 0;
  16.         for (; v > 0; v = v / base)
  17.             push_back(v % base);
  18.         return *this;
  19.     }
  20.  
  21.     bigint operator+(const bigint &v) const {
  22.         bigint res = v;
  23.  
  24.         for (int i = 0, carry = 0; i < (int) max(zs, v.zs) || carry; ++i) {
  25.             if (i == (int) res.zs)
  26.                 res.push_back(0);
  27.             res.z[i] += carry + (i < (int) zs ? z[i] : 0);
  28.             carry = res.z[i] >= base;
  29.             if (carry)
  30.                 res.z[i] -= base;
  31.         }
  32.         return res;
  33.     }
  34.  
  35.     bigint operator-(const bigint &v) const {
  36.         bigint res = *this;
  37.         for (int i = 0, carry = 0; i < (int) v.zs || carry; ++i) {
  38.             res.z[i] -= carry + (i < (int) v.zs ? v.z[i] : 0);
  39.             carry = res.z[i] < 0;
  40.             if (carry)
  41.                 res.z[i] += base;
  42.         }
  43.         res.trim();
  44.         return res;
  45.     }
  46.  
  47.     bigint& operator+=(const bigint &v) {
  48.         return *this = *this + v;
  49.     }
  50.  
  51.     void trim() {
  52.         while (zs != 0 && z[zs-1] == 0)
  53.             zs--;
  54.     }
  55.  
  56.     bigint operator*(const bigint &v) const {
  57.         static long long vres[30];
  58.         memset(vres, 0, sizeof(vres[0]) * (zs + v.zs));
  59.         for (int i = 0; i < zs; i++) {
  60.             for (int j = 0; j < v.zs; j++) {
  61.                 vres[i + j] += (long long)z[i] * (long long)v.z[j];
  62.             }
  63.         }
  64.  
  65.         bigint res;
  66.         for (int i = 0, carry = 0; i < zs + v.zs; i++) {
  67.             long long cur = vres[i] + carry;
  68.             res.push_back((int) (cur % base));
  69.             carry = (int) (cur / base);
  70.         }
  71.         res.trim();
  72.         return res;
  73.     }
  74.  
  75.     void push_back(long long i) {
  76.         z[zs++] = i;
  77.     }
  78.  
  79.     friend ostream& operator<<(ostream &stream, const bigint &v) {
  80.         stream << (v.zs == 0 ? 0 : v.z[v.zs - 1]);
  81.         for (int i = (int) v.zs - 2; i >= 0; --i)
  82.             stream << setw(base_digits) << setfill('0') << v.z[i];
  83.         return stream;
  84.     }
  85. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement