API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Apr 21st, 2019
74
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 21.97 KB | None | 0 0
raw download clone embed print report
  1. #include <cstring>
  2. #include <math.h>
  3. #include <cstdio>
  4. #include <iostream>
  5. #include <iomanip>
  6. #include <string>
  7. using namespace std;
  8.  
  9. class BigIntegerOverflow : std::exception{
  10. };
  11.  
  12. class BigInt {
  13.     friend ostream& operator <<(ostream&, const BigInt&);
  14.     friend istream& operator >>(istream&, BigInt&);
  15.     friend BigInt operator / (const BigInt&, const BigInt&);
  16.     friend BigInt operator % (const BigInt&, const BigInt&);
  17.     friend BigInt big_sqrt (const BigInt&);
  18.     friend bool operator <= (const BigInt& left, const BigInt& right);
  19.     friend bool operator >= (const BigInt& left, const BigInt& right);
  20.     friend bool operator != (const BigInt& left, const BigInt& right);
  21.     friend BigInt operator + (const BigInt& left, const BigInt& right);
  22.     friend BigInt operator * (const BigInt& left, const BigInt& right);
  23.     friend BigInt operator - (const BigInt& left, const BigInt& right);
  24.     friend bool operator == (const BigInt& left, const BigInt& right);
  25.     friend bool operator < (const BigInt& left, const BigInt& right);
  26.     friend bool operator > (const BigInt& left, const BigInt& right);
  27. private:
  28.     int* data;
  29.     bool sign;
  30.     int lenght;
  31. public:
  32.     BigInt(unsigned int);
  33.     BigInt(long long);
  34.     BigInt(unsigned long long);
  35.     BigInt(int);
  36.     ~BigInt();
  37.     BigInt(const string&);
  38.     BigInt();
  39.     BigInt(const BigInt&);
  40.     BigInt& operator =(const BigInt& big_int);
  41.     BigInt& operator++ ();
  42.     BigInt& operator-- ();
  43.     const BigInt operator++ (int);
  44.     const BigInt operator-- (int);
  45.     BigInt& operator += (const BigInt& right);
  46.     BigInt& operator -= (const BigInt& right);
  47.     BigInt& operator *= (const BigInt& right);
  48.     BigInt operator - ();
  49.     BigInt& operator + ();
  50. };
  51.  
  52. int MAX_LENGTH = 50000;
  53. int LENGTH_LIMIT = 21000;
  54.  
  55. void reverse_array (int* arr, int length){
  56.     for (int i = 0; i < length / 2; ++i){
  57.         swap(arr[i], arr[length - 1 - i]);
  58.     }
  59. }
  60.  
  61. BigInt& BigInt::operator+=(const BigInt &right) {
  62.     *this = *this + right;
  63.     return *this;
  64. }
  65.  
  66. BigInt& BigInt::operator+() {
  67.     return *this;
  68. }
  69.  
  70. BigInt& BigInt::operator*=(const BigInt &right) {
  71.     *this = *this * right;
  72.     return *this;
  73. }
  74.  
  75. BigInt BigInt::operator-() {
  76.     return (*this * (-1));
  77. }
  78.  
  79. bool operator != (const BigInt& left, const BigInt& right){
  80.     return !(left == right);
  81. }
  82.  
  83. bool operator <= (const BigInt& left, const BigInt& right){
  84.     return !(left > right);
  85. }
  86.  
  87. bool operator >= (const BigInt& left, const BigInt& right){
  88.     return !(left < right);
  89. }
  90.  
  91. BigInt& BigInt::operator-=(const BigInt &right) {
  92.     *this = *this - right;
  93.     return *this;
  94. }
  95.  
  96. BigInt& BigInt::operator++() {
  97.     *this += 1;
  98.     return *this;
  99. }
  100.  
  101. BigInt& BigInt::operator--() {
  102.     *this -= 1;
  103.     return *this;
  104. }
  105.  
  106. const BigInt BigInt::operator++(int) {
  107.     const BigInt temp = *this;
  108.     *this += 1;
  109.     return temp;
  110. }
  111.  
  112. const BigInt BigInt::operator--(int) {
  113.     const BigInt temp = *this;
  114.     *this -= 1;
  115.     return temp;
  116. }
  117.  
  118. BigInt::BigInt() {
  119.     data = new int[MAX_LENGTH];
  120.     for (int i = 0; i < MAX_LENGTH; ++i){
  121.         data[i] = 0;
  122.     }
  123.     lenght = 0;
  124.     sign = true;
  125. }
  126.  
  127. BigInt::BigInt(long long k) {
  128.     data = new int [MAX_LENGTH];
  129.     if (k == 0){
  130.         data[0] = 0;
  131.         lenght = 1;
  132.         sign = true;
  133.         return;
  134.     }
  135.     for (int i = 0; i < MAX_LENGTH; ++i){
  136.         data[i] = 0;
  137.     }
  138.     if (k < 0){
  139.         sign = false;
  140.         k *= -1;
  141.     }
  142.     else{
  143.         sign = true;
  144.     }
  145.     int digit;
  146.     int count_of_digits = 0;
  147.     while(k > 0){
  148.         digit = k % 10;
  149.         k = k / 10;
  150.         data[count_of_digits] = digit;
  151.         ++count_of_digits;
  152.     }
  153.     for (int i = 0; i < count_of_digits / 2; ++i){
  154.         swap(data[i], data[count_of_digits - i - 1]);
  155.     }
  156.     lenght = count_of_digits;
  157. }
  158.  
  159. BigInt::BigInt(unsigned int k) {
  160.     data = new int [MAX_LENGTH];
  161.     if (k == 0){
  162.         data[0] = 0;
  163.         lenght = 1;
  164.         sign = true;
  165.         return;
  166.     }
  167.     for (int i = 0; i < MAX_LENGTH; ++i){
  168.         data[i] = 0;
  169.     }
  170.     if (k < 0){
  171.         sign = false;
  172.         k *= -1;
  173.     }
  174.     else{
  175.         sign = true;
  176.     }
  177.     int digit;
  178.     int count_of_digits = 0;
  179.     while(k > 0){
  180.         digit = k % 10;
  181.         k = k / 10;
  182.         data[count_of_digits] = digit;
  183.         ++count_of_digits;
  184.     }
  185.     for (int i = 0; i < count_of_digits / 2; ++i){
  186.         swap(data[i], data[count_of_digits - i - 1]);
  187.     }
  188.     lenght = count_of_digits;
  189. }
  190.  
  191. BigInt::BigInt(unsigned long long k) {
  192.     data = new int [MAX_LENGTH];
  193.     if (k == 0){
  194.         data[0] = 0;
  195.         lenght = 1;
  196.         sign = true;
  197.         return;
  198.     }
  199.     for (int i = 0; i < MAX_LENGTH; ++i){
  200.         data[i] = 0;
  201.     }
  202.     if (k < 0){
  203.         sign = false;
  204.         k *= -1;
  205.     }
  206.     else{
  207.         sign = true;
  208.     }
  209.     int digit;
  210.     int count_of_digits = 0;
  211.     while(k > 0){
  212.         digit = k % 10;
  213.         k = k / 10;
  214.         data[count_of_digits] = digit;
  215.         ++count_of_digits;
  216.     }
  217.     for (int i = 0; i < count_of_digits / 2; ++i){
  218.         swap(data[i], data[count_of_digits - i - 1]);
  219.     }
  220.     lenght = count_of_digits;
  221. }
  222.  
  223. BigInt::BigInt(const string& str) {
  224.     data = new int [MAX_LENGTH];
  225.     for (int i = 0; i < MAX_LENGTH; ++i){
  226.         data[i] = 0;
  227.     }
  228.     if (str[0] == '-'){
  229.         lenght = str.size() - 1;
  230.         if (lenght > LENGTH_LIMIT){
  231.             throw BigIntegerOverflow();
  232.         }
  233.         sign = false;
  234.         for (int i = 0; i < lenght; ++i){
  235.             data[i] = str[i + 1] - 48;
  236.         }
  237.     }
  238.     else{
  239.         sign = true;
  240.         lenght = str.size();
  241.         if (lenght > LENGTH_LIMIT){
  242.             throw BigIntegerOverflow();
  243.         }
  244.         for (int i = 0; i < lenght; ++i){
  245.             data[i] = str[i] - 48;
  246.         }
  247.     }
  248. }
  249.  
  250. BigInt::BigInt(int k) {
  251.     data = new int [MAX_LENGTH];
  252.     if (k == 0){
  253.         data[0] = 0;
  254.         lenght = 1;
  255.         sign = true;
  256.         return;
  257.     }
  258.     for (int i = 0; i < MAX_LENGTH; ++i){
  259.         data[i] = 0;
  260.     }
  261.     if (k < 0){
  262.         sign = false;
  263.         k *= -1;
  264.     }
  265.     else{
  266.         sign = true;
  267.     }
  268.     int digit;
  269.     int count_of_digits = 0;
  270.     while(k > 0){
  271.         digit = k % 10;
  272.         k = k / 10;
  273.         data[count_of_digits] = digit;
  274.         ++count_of_digits;
  275.     }
  276.     for (int i = 0; i < count_of_digits / 2; ++i){
  277.         swap(data[i], data[count_of_digits - i - 1]);
  278.     }
  279.     lenght = count_of_digits;
  280. }
  281.  
  282.  
  283. istream& operator >> (istream& in, BigInt& big_int){
  284.     string str;
  285.     cin >> str;
  286.     big_int = BigInt(str);
  287.     return in;
  288. }
  289.  
  290. ostream& operator << (ostream& out, const BigInt& B_INT){
  291.     if (! B_INT.sign){
  292.         cout << "-";
  293.         for (int i = 0; i < B_INT.lenght; ++i){
  294.             cout << B_INT.data[i];
  295.         }
  296.     }
  297.     else{
  298.         for (int i = 0; i < B_INT.lenght; ++i){
  299.             cout << B_INT.data[i];
  300.         }
  301.     }
  302.     return out;
  303. }
  304.  
  305. BigInt::~BigInt() {
  306.     delete[] data;
  307. }
  308.  
  309. BigInt& BigInt::operator = (const BigInt& big_int){
  310.     if (this == &big_int){
  311.         return *this;
  312.     }
  313.     for (int i = 0 ; i < this->lenght; ++i){
  314.         data[i] = 0;
  315.     }
  316.     lenght = big_int.lenght;
  317.     sign = big_int.sign;
  318.     for (int i = 0; i < lenght; ++i){
  319.         data[i] = big_int.data[i];
  320.     }
  321.     return *this;
  322. }
  323.  
  324. BigInt::BigInt(const BigInt& big_int) {
  325.     data = new int [MAX_LENGTH];
  326.     for (int i = 0; i < MAX_LENGTH; ++i){
  327.         data[i] = 0;
  328.     }
  329.     lenght = big_int.lenght;
  330.     sign = big_int.sign;
  331.     for (int i = 0; i < lenght; ++i){
  332.         data[i] = big_int.data[i];
  333.     }
  334. }
  335.  
  336. BigInt operator + (const BigInt& l, const BigInt& r) {
  337.     BigInt left = l, right = r;
  338.     BigInt result;
  339.     if (left.sign && right.sign) {
  340.         if (left.lenght > right.lenght) {
  341.             result.lenght = left.lenght + 1;
  342.         } else {
  343.             result.lenght = right.lenght + 1;
  344.         }
  345.         for (int i = 0; i < result.lenght; ++i) {
  346.             result.data[i] = 0;
  347.         }
  348.         reverse_array(left.data, left.lenght);
  349.         reverse_array(right.data, right.lenght);
  350.         for (int i = 0; i < result.lenght - 1; ++i) {
  351.             result.data[i] += left.data[i] + right.data[i];
  352.             result.data[i + 1] += (result.data[i] / 10);
  353.             result.data[i] %= 10;
  354.         }
  355.         if (result.data[result.lenght - 1] == 0) {
  356.             result.lenght -= 1;
  357.         }
  358.         reverse_array(left.data, left.lenght);
  359.         reverse_array(right.data, right.lenght);
  360.         reverse_array(result.data, result.lenght);
  361.         result.sign = true;
  362.         if (result.lenght > LENGTH_LIMIT){
  363.             throw BigIntegerOverflow();
  364.         }
  365.         return result;
  366.     }
  367.     else{
  368.         if (!left.sign && right.sign) {
  369.             BigInt temp = left;
  370.             temp.sign = true;
  371.             result = right - temp;
  372.             if (result.lenght > LENGTH_LIMIT){
  373.                 throw BigIntegerOverflow();
  374.             }
  375.             return result;
  376.         }
  377.         if(left.sign && !right.sign){
  378.             BigInt temp = right;
  379.             temp.sign = true;
  380.             result = left - temp;
  381.             if (result.lenght > LENGTH_LIMIT){
  382.                 throw BigIntegerOverflow();
  383.             }
  384.             return result;
  385.         }
  386.         if(!left.sign && !right.sign){
  387.             BigInt temp = right;
  388.             temp.sign = true;
  389.             result = left - temp;
  390.             if (result.lenght > LENGTH_LIMIT){
  391.                 throw BigIntegerOverflow();
  392.             }
  393.             return result;
  394.         }
  395.     }
  396. }
  397.  
  398. bool operator ==(const BigInt& left, const BigInt & right){
  399.     if(left.sign != right.sign){
  400.         return false;
  401.     }
  402.     if(left.lenght != right.lenght){
  403.         return false;
  404.     }
  405.     for (int i = 0; i < left.lenght; ++i) {
  406.         if (left.data[i] != right.data[i]) {
  407.             return false;
  408.         }
  409.     }
  410.     return true;
  411. }
  412.  
  413. bool operator< (const BigInt& left, const BigInt& right){
  414.     if (left == right){
  415.         return false;
  416.     }
  417.     if (left.sign && ! right.sign){
  418.         return false;
  419.     }
  420.     if (! left.sign && right.sign){
  421.         return true;
  422.     }
  423.     if (left.sign && right.sign){
  424.         if (left.lenght < right.lenght){
  425.             return true;
  426.         }
  427.         if (left.lenght > right.lenght){
  428.             return false;
  429.         }
  430.     }
  431.     if (! left.sign and ! right.sign){
  432.         if (left.lenght < right.lenght){
  433.             return false;
  434.         }
  435.         if (left.lenght > right.lenght){
  436.             return true;
  437.         }
  438.     }
  439.     for(int i = 0; i < left.lenght; ++i){
  440.         if (left.data[i] < right.data[i]){
  441.             if (left.sign){
  442.                 return true;
  443.             }
  444.             else{
  445.                 return false;
  446.             }
  447.         }
  448.         if (left.data[i] == right.data[i]){
  449.             continue;
  450.         }
  451.         if (left.data[i] > right.data[i]){
  452.             if(left.sign){
  453.                 return false;
  454.             }
  455.             else {
  456.                 return true;
  457.             }
  458.         }
  459.     }
  460. }
  461.  
  462. bool operator> (const BigInt& left, const BigInt& right) {
  463.     if (left == right){
  464.         return false;
  465.     }
  466.     if (left < right){
  467.         return false;
  468.     }
  469.     return true;
  470. }
  471.  
  472. void difference (const int *x, const int *y, int *z, int length) {
  473.     int* copy_of_x = new int[length];
  474.     for (int i = 0; i < length; ++i){
  475.         copy_of_x[i] = x[i];
  476.     }
  477.     for (int i = 0; i <= (length - 1); i++)
  478.     {
  479.         if (i < (length - 1))
  480.         {
  481.             --copy_of_x[i + 1];
  482.             z[i] += 10 + copy_of_x[i];
  483.         }
  484.         else{
  485.             z[i] += copy_of_x[i];
  486.         }
  487.  
  488.         z[i] -= y[i];
  489.  
  490.         if (z[i] / 10 > 0){
  491.             z[i + 1]++;
  492.             z[i] %= 10;
  493.         }
  494.     }
  495.     delete[] copy_of_x;
  496. }
  497.  
  498. BigInt operator- (const BigInt& l, const BigInt& r) {
  499.     BigInt left = l, right = r;
  500.     BigInt result;
  501.     if (left == right){
  502.         result = 0;
  503.         return result;
  504.     }
  505.     if (left.sign && right.sign) {
  506.         if (left > right) {
  507.             result.lenght = left.lenght;
  508.             reverse_array(left.data, left.lenght);
  509.             reverse_array(right.data, right.lenght);
  510.             difference(left.data, right.data, result.data, left.lenght);
  511.             for (int i = left.lenght - 1; i >= 0; --i) {
  512.                 if (result.data[i] == 0) {
  513.                     --result.lenght;
  514.                     continue;
  515.                 } else {
  516.                     break;
  517.                 }
  518.             }
  519.             reverse_array(left.data, left.lenght);
  520.             reverse_array(right.data, right.lenght);
  521.             reverse_array(result.data, result.lenght);
  522.             result.sign = true;
  523.             return result;
  524.         }
  525.         if (left < right) {
  526.             result.lenght = right.lenght;
  527.             reverse_array(left.data, left.lenght);
  528.             reverse_array(right.data, right.lenght);
  529.             difference(right.data, left.data, result.data, right.lenght);
  530.             for (int i = right.lenght - 1; i >= 0; --i) {
  531.                 if (result.data[i] == 0) {
  532.                     --result.lenght;
  533.                     continue;
  534.                 } else {
  535.                     break;
  536.                 }
  537.             }
  538.             reverse_array(left.data, left.lenght);
  539.             reverse_array(right.data, right.lenght);
  540.             reverse_array(result.data, result.lenght);
  541.             result.sign = false;
  542.             return result;
  543.         }
  544.     }
  545.     if (left.sign && !right.sign){
  546.         BigInt temp = right;
  547.         temp.sign = true;
  548.         result = left + temp;
  549.         return result;
  550.     }
  551.     if (!left.sign && right.sign){
  552.         BigInt temp = left;
  553.         temp.sign = true;
  554.         result = temp + right;
  555.         result.sign = false;
  556.         return result;
  557.     }
  558.     if (!left.sign && !right.sign) {
  559.         BigInt temp_right = left;
  560.         BigInt temp_left = right;
  561.         temp_left.sign = true;
  562.         temp_right.sign = true;
  563.         // result = right - left
  564.         if (temp_left > temp_right){
  565.             result.lenght = temp_left.lenght;
  566.             reverse_array(temp_left.data, temp_left.lenght);
  567.             reverse_array(temp_right.data, temp_right.lenght);
  568.             difference(temp_left.data, temp_right.data, result.data, temp_left.lenght);
  569.             for(int i = temp_left.lenght - 1; i >= 0; --i){
  570.                 if(result.data[i] == 0){
  571.                     --result.lenght;
  572.                     continue;
  573.                 }
  574.                 else{
  575.                     break;
  576.                 }
  577.             }
  578.             reverse_array(temp_left.data, temp_left.lenght);
  579.             reverse_array(temp_right.data, temp_right.lenght);
  580.             reverse_array(result.data, result.lenght);
  581.             result.sign = true;
  582.             return result;
  583.         }
  584.         if (temp_left < temp_right){
  585.             result.lenght = temp_right.lenght;
  586.             reverse_array(temp_left.data, temp_left.lenght);
  587.             reverse_array(temp_right.data, temp_right.lenght);
  588.             difference(temp_right.data, temp_left.data, result.data, temp_right.lenght);
  589.             for(int i = temp_right.lenght - 1; i >= 0; --i){
  590.                 if(result.data[i] == 0){
  591.                     --result.lenght;
  592.                     continue;
  593.                 }
  594.                 else{
  595.                     break;
  596.                 }
  597.             }
  598.             reverse_array(temp_left.data, temp_left.lenght);
  599.             reverse_array(temp_right.data, temp_right.lenght);
  600.             reverse_array(result.data, result.lenght);
  601.             result.sign = false;
  602.             return result;
  603.         }
  604.     }
  605. }
  606.  
  607. BigInt operator* (const BigInt& l, const BigInt& r){
  608.     BigInt left = l, right = r;
  609.     BigInt result;
  610.     if (left == 0 || right == 0){
  611.         result = 0;
  612.         result.sign = true;
  613.         return result;
  614.     }
  615.     result.lenght = left.lenght + right.lenght + 1;
  616.     reverse_array(left.data, left.lenght);
  617.     reverse_array(right.data, right.lenght);
  618.     for (int i = 0; i < left.lenght; ++i) {
  619.         for (int j = 0; j < right.lenght; ++j) {
  620.             result.data[i + j] += left.data[i] * right.data[j];
  621.         }
  622.     }
  623.     for (int i = 0; i < result.lenght - 1; ++i) {
  624.         result.data[i + 1] +=  result.data[i] / 10;
  625.         result.data[i] %= 10;
  626.     }
  627.     while(result.data[result.lenght - 1] == 0){
  628.         --result.lenght;
  629.     }
  630.     if (result.lenght == 0){
  631.         ++result.lenght;
  632.     }
  633.     reverse_array(left.data, left.lenght);
  634.     reverse_array(right.data, right.lenght);
  635.     reverse_array(result.data, result.lenght);
  636.     if (left.sign != right.sign){
  637.         result.sign = false;
  638.     }
  639.     else{
  640.         result.sign = true;
  641.     }
  642.     if (result.lenght > LENGTH_LIMIT){
  643.         throw BigIntegerOverflow();
  644.     }
  645.     return result;
  646. }
  647.  
  648. BigInt operator / (const BigInt& left, const BigInt& right){
  649.     if (right == 1){
  650.         return left;
  651.     }
  652.     if (left.lenght == right.lenght){
  653.         BigInt result;
  654.         int k = 1;
  655.         while (right * k < left || right * k == left) {
  656.             ++k;
  657.         }
  658.         --k;
  659.         result = k;
  660.         return result;
  661.     }
  662.     BigInt temp_left = left, temp_right = right;
  663.     temp_left.sign = true;
  664.     temp_right.sign = true;
  665.     BigInt result;
  666.     int counter = 0;
  667.     if (temp_right.lenght > temp_left.lenght){
  668.         result = 0;
  669.         return result;
  670.     }
  671.     result.lenght = temp_left.lenght;
  672.     BigInt temp;
  673.     temp.lenght = temp_right.lenght;
  674.     for(int i = 0; i < temp_right.lenght; ++i){
  675.         temp.data[i] = temp_left.data[i];
  676.     }
  677.  
  678.     int calls = 0;
  679.     for (int i = temp_right.lenght; i < temp_left.lenght;) {
  680.         while (temp < temp_right) {
  681.             if (calls == 0) {
  682.                 if (temp.data[0] == 0) {
  683.                     temp.data[0] = temp_left.data[i];
  684.                     if (temp.data[0] == 0) {
  685.                         result.data[counter] = 0;
  686.                         ++counter;
  687.                     }
  688.                     ++calls;
  689.                     ++i;
  690.                     if (i == temp_left.lenght) {
  691.                         break;
  692.                     }
  693.                 } else {
  694.                     ++temp.lenght;
  695.                     temp.data[temp.lenght - 1] = temp_left.data[i];
  696.                     ++i;
  697.                     ++calls;
  698.                     if (i == temp_left.lenght) {
  699.                         break;
  700.                     }
  701.                 }
  702.             }
  703.             else {
  704.                 if (temp.data[0] == 0) {
  705.                     temp.data[0] = temp_left.data[i];
  706.                     if (temp.data[0] == 0) {
  707.                         result.data[counter] = 0;
  708.                         ++counter;
  709.                     }
  710.                     ++i;
  711.                     ++calls;
  712.                     if (i == temp_left.lenght) {
  713.                         break;
  714.                     }
  715.                 } else {
  716.                     ++temp.lenght;
  717.                     temp.data[temp.lenght - 1] = temp_left.data[i];
  718.                     ++i;
  719.                     ++calls;
  720.                     result.data[counter] = 0;
  721.                     ++counter;
  722.                     if (i == temp_left.lenght) {
  723.                         break;
  724.                     }
  725.                 }
  726.             }
  727.         }
  728.         int k = 1;
  729.         while (temp_right * k < temp || temp_right * k == temp) {
  730.             ++k;
  731.         }
  732.         --k;
  733.         if (k != 0) {
  734.             temp = temp - temp_right * k;
  735.             result.data[counter] = k;
  736.             ++counter;
  737.             calls = 0;
  738.         }
  739.         else{
  740.             if (temp.data[0] != 0){
  741.                 result.data[counter] = 0;
  742.                 ++counter;
  743.             }
  744.             break;
  745.         }
  746.     }
  747.     result.lenght = counter;
  748.     return result;
  749. }
  750.  
  751. BigInt operator % (const BigInt& left, const BigInt& right){
  752.     BigInt temp;
  753.     temp = left / right;
  754.     return left - temp * right;
  755. }
  756.  
  757. BigInt NOD(const BigInt& left, const BigInt& right){
  758.     BigInt temp_right = right, temp_left = left;
  759.     BigInt temp;
  760.     if(temp_left > temp_right){
  761.         while(true){
  762.             if (temp_left % temp_right == 0){
  763.                 return temp_right;
  764.             }
  765.             temp = temp_right;
  766.             temp_right = temp_left % temp_right;
  767.             temp_left = temp;
  768.         }
  769.     }
  770.     else{
  771.         while(true){
  772.             if (temp_right % temp_left == 0){
  773.                 return temp_left;
  774.             }
  775.             temp = temp_left;
  776.             temp_left = temp_right % temp_left;
  777.             temp_right = temp;
  778.         }
  779.     }
  780. }
  781.  
  782. BigInt big_sqrt(const BigInt& big_int){
  783.     BigInt result, temp;
  784.     result.lenght = (big_int.lenght + 1) / 2;
  785.     for(int i = 0; i < result.lenght; ++i){
  786.         for(int j = 9; j >= 0; --j){
  787.             result.data[i] = j;
  788.             temp = result;
  789.             if (result*temp < big_int || result*temp == big_int){
  790.                 break;
  791.             }
  792.         }
  793.     }
  794.     return result;
  795. }
  796.  
  797. int main() {
  798.     try {
  799.         std::ios_base::sync_with_stdio(false);
  800.         std::cin.tie(nullptr);
  801.         BigInt a, b;
  802.         std::cin >> a >> b;
  803.         int c;
  804.         std::cin >> c;
  805.  
  806.         std::cout << (a * c == c * b) << '\n';
  807.         std::cout << (a + 5 < b) << '\n';
  808.         std::cout << (a <= b) << '\n';
  809.         std::cout << (a > b - 5) << '\n';
  810.         std::cout << (a >= b - 5) << '\n';
  811.         std::cout << (a != b * c) << '\n';
  812.         std::cout << (a == -b) << '\n';
  813.  
  814.         BigInt d("123"), e(1ULL << 63);
  815.         std::cout << (d + c) * e << '\n';
  816.  
  817.         try {
  818.             a += b;
  819.             b = a - b;
  820.             a -= b;
  821.             std::cout << a + b << '\n';
  822.             std::cout << a - b << '\n';
  823.             std::cout << a * b << '\n';
  824.         } catch (BigIntegerOverflow) {
  825.             std::cout << "Overflow" << '\n';
  826.         }
  827.     } catch (const BigIntegerOverflow&){
  828.         cout << "opana";
  829.     }
  830. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!