Advertisement
TrickmanOff

Untitled

Jul 28th, 2019
242
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.16 KB | None | 0 0
  1.  
  2. /*
  3. Поддерживает следующие функции:
  4. Положительные и отрицательные числа:
  5. Чтение
  6. Вывод
  7. Сложение
  8. Вычитание
  9. Унарный минус
  10. Умножение
  11. Неотрицательные:
  12. Максимум
  13. */
  14. ////////////////////
  15. const int POW10 = 1000 * 1000 * 1000;
  16.  
  17. void check(bool e) {
  18.     if (!e)
  19.         throw 1;
  20. }
  21.  
  22. void skip_sym() {
  23.     int c = cin.peek();
  24.     while (c == ' ' || c == '\r' || c == '\n' || c == '\t') {
  25.         cin.get();
  26.         c = cin.peek();
  27.     }
  28. }
  29.  
  30. struct UInt {
  31. //constructor UInt(vector<int> &digits) builds UInt via vector of POW10-based nums
  32. //read() - reads UInt and returns it
  33. //size() - returns size of POW10-based digits
  34. //operator[index] - returns index POW10-based num
  35. //print() - prints UInt
  36. //isZero() - returns true if UInt == 0
  37.     vector<int> digits;
  38.  
  39.     UInt(const vector<int>& digits) : digits(digits) {
  40.         check(digits.size() > 0);
  41.         check(digits.size() == 1 || digits.back() > 0);
  42.         for (int digit : digits)
  43.             check(digit >= 0 || digit < POW10);
  44.     }
  45.  
  46.     int size() const {
  47.         return (int)digits.size();
  48.     }
  49.  
  50.     static UInt read() {
  51.         skip_sym();
  52.         vector<char> source;
  53.  
  54.         int c = cin.get();
  55.         check(c >= '0' && c <= '9');
  56.  
  57.         while (c >= '0' && c <= '9') {
  58.             source.push_back(c);
  59.             c = cin.get();
  60.         }
  61.  
  62.         cin.unget();
  63.  
  64.         vector<int> digits;
  65.         int n = 0;
  66.         int pow10 = 1;
  67.         for (int i = source.size() - 1; i >= 0; i--) {
  68.             n += (source[i] - '0') * pow10;
  69.             pow10 *= 10;
  70.             if (pow10 == POW10) {
  71.                 digits.push_back(n);
  72.                 n = 0;
  73.                 pow10 = 1;
  74.             }
  75.         }
  76.  
  77.         if(pow10 > 1)
  78.             digits.push_back(n);
  79.  
  80.         return UInt(digits);
  81.     }
  82.  
  83.     int operator[] (const int index) const {
  84.         check(index >= 0);
  85.         if (index < digits.size())
  86.             return digits[index];
  87.         else
  88.             return 0;
  89.     }
  90.  
  91.     void print() const {
  92.         cout << digits.back();
  93.  
  94.         for (int i = digits.size() - 2; i >= 0; i--)
  95.             for (int pow = POW10/10; pow >= 1; pow /= 10)
  96.                 cout << digits[i] / pow % 10;
  97.     }
  98.  
  99.     bool isZero() const{
  100.         return (digits.size() == 1 && digits[0] == 0);
  101.     }
  102. };
  103.  
  104. const UInt UInt_ZERO = UInt(vector<int> {0});
  105.  
  106. int compare(const UInt& left, const UInt& right) {
  107.     //returns negative num if (left < right), null if (left == right), positive num if(left > right)
  108.     if (left.size() != right.size())
  109.         return left.size() - right.size();
  110.  
  111.     for (int i = left.size()-1; i >= 0; i--) {
  112.         if (left[i] != right[i]) {
  113.             return left[i] - right[i];
  114.         }
  115.     }
  116.  
  117.     return 0;
  118. }
  119.  
  120. UInt operator + (const UInt& left, const UInt& right) {
  121.     vector<int> digits;
  122.     int carry = 0;
  123.     for (int i = 0; i < std::max(left.size(), right.size()) || carry != 0; i++) {
  124.         carry += left[i] + right[i];
  125.         digits.push_back(carry % POW10);
  126.         carry /= POW10;
  127.     }
  128.     check(carry == 0);
  129.     return UInt(digits);
  130. }
  131.  
  132. UInt operator - (const UInt& left, const UInt& right) {
  133.     //left > right
  134.     vector<int> digits;
  135.     int carry = 0;
  136.     for (int i = 0; i < left.size(); i++) {
  137.         carry += left[i] - right[i] + POW10;
  138.         digits.push_back(carry % POW10);
  139.         carry /= POW10;
  140.         carry--;
  141.     }
  142.  
  143.  
  144.     //delete leading nulls
  145.     while ((int) digits.size() > 1 && digits.back() == 0)
  146.         digits.pop_back();
  147.  
  148.     return UInt(digits);
  149. }
  150.  
  151. UInt operator * (const UInt& left, const UInt& right) {
  152.     if (left.isZero() || right.isZero())
  153.         return UInt_ZERO;
  154.  
  155.     vector<int> digits;
  156.     ll carry = 0;
  157.  
  158.     for (int j = 0; j < right.size(); j++) {
  159.         for (int i = 0; i < left.size() || carry != 0; i++) {
  160.             if (i + j >= digits.size())
  161.                 digits.push_back(0);
  162.  
  163.             carry += 1LL * left[i] * right[j] + digits[i+j];
  164.             digits[i+j] = carry % POW10;
  165.  
  166.             carry /= POW10;
  167.         }
  168.     }
  169.  
  170.     return UInt(digits);
  171. }
  172.  
  173. UInt max(const UInt& a, const UInt& b) {
  174.     //returns maximum UInt of two given UInt nums
  175.     if (compare(a, b) > 0)
  176.         return a;
  177.     else
  178.         return b;
  179. }
  180.  
  181. UInt min(const UInt& a, const UInt& b) {
  182.     if (compare(a, b) > 0)
  183.         return b;
  184.     else
  185.         return a;
  186. }
  187.  
  188. UInt max(const std::initializer_list<UInt> list) {
  189.     //returns maximum UInt of given UInt list
  190.     UInt cur_max = *list.begin();
  191.  
  192.     for (auto ptr = list.begin() + 1; ptr < list.end(); ptr++) {
  193.         if (compare(*ptr, cur_max) > 0)
  194.             cur_max = *ptr;
  195.     }
  196.  
  197.     return cur_max;
  198. }
  199.  
  200. struct Int {
  201.     //negate() - returns Int with opposite sign
  202.     UInt modulus;
  203.  
  204.     int sign; // -1/0/1
  205.  
  206.     Int(const UInt &modulus, const int sign) : modulus(modulus), sign(sign) {
  207.         check(sign == 0 || sign == -1 || sign == 1);
  208.         check(sign != 0 || modulus.isZero());
  209.     }
  210.  
  211.     static Int read() {
  212.         skip_sym();
  213.  
  214.         int c = cin.peek();
  215.         int sign = 1;
  216.  
  217.         if (c == '-') {
  218.             sign = -1;
  219.             cin.get();
  220.         }
  221.  
  222.         UInt modulus = UInt::read();
  223.         if (modulus.isZero())
  224.             sign = 0;
  225.  
  226.        
  227.  
  228.         return Int(modulus, sign);
  229.     }
  230.  
  231.     void print() const {
  232.         if (sign == -1)
  233.             cout << '-';
  234.  
  235.         modulus.print();
  236.     }
  237.  
  238.     bool isZero() const {
  239.         return sign == 0;
  240.     }
  241.  
  242. };
  243.  
  244. Int operator - (const Int& num)  {
  245.     return Int(num.modulus, -num.sign);
  246. }
  247.  
  248. Int operator - (const Int& left, const Int& right) {
  249.     if (right.isZero())
  250.         return left;
  251.     if (left.isZero())
  252.         return -right;
  253.  
  254.     //if different sign -3 - 4     3 - (-4), add them
  255.     if (left.sign != right.sign) {
  256.         return Int(left.modulus + right.modulus, left.sign);
  257.     }
  258.     //if the same sign -3 - (-4) = 1      3 - 4 = -1
  259.     int cmp = compare(left.modulus, right.modulus);
  260.     if (cmp == 0)
  261.         return Int(UInt_ZERO, 0);
  262.     else if (cmp < 0)
  263.         return Int(right.modulus - left.modulus, -left.sign);
  264.     else {
  265.         check(cmp > 0);
  266.         return Int(left.modulus - right.modulus, left.sign);
  267.     }
  268. }
  269.  
  270. Int operator + (const Int& left, const Int& right) {
  271.     if (left.isZero())
  272.         return right;
  273.     if (right.isZero())
  274.         return left;
  275.  
  276.     if (left.sign == right.sign)
  277.         return Int(left.modulus + right.modulus, left.sign);
  278.  
  279.     int cmp = compare(left.modulus, right.modulus);
  280.     if (cmp < 0)
  281.         return Int(right.modulus - left.modulus, right.sign);
  282.     else if (cmp == 0)
  283.         return Int(UInt_ZERO, 0);
  284.     else
  285.         return Int(left.modulus - right.modulus, left.sign);
  286. }
  287.  
  288. Int operator * (const Int& left, const Int& right) {
  289.     if (left.sign == 0 || right.sign == 0)
  290.         return Int(UInt_ZERO, 0);
  291.  
  292.     if (left.sign == right.sign)
  293.         return Int(left.modulus * right.modulus, 1);
  294.     else
  295.         return Int(left.modulus * right.modulus, -1);
  296. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement