Advertisement
Guest User

bigint

a guest
Apr 7th, 2020
183
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 13.13 KB | None | 0 0
  1. #include <cstring>
  2. #include <math.h>
  3. #include <cstdio>
  4. #include <iostream>
  5. #include <iomanip>
  6.  
  7. #include <utility>
  8.  
  9. typedef uint64_t digit_type;
  10.  
  11. using namespace std;
  12.  
  13. size_t ConvertToBase(digit_type* arrN, digit_type N, digit_type kBase);
  14.  
  15. class BigIntegerOverflow {
  16. };
  17.  
  18. class BigInteger {
  19. private:
  20.     const static size_t maxLength_ = 3000; // number of digits, количество болок по baselog цифр
  21.     const static uint8_t baseLog_ = 9; // use 1 or 2 for debug, по умлчанию 9
  22.  
  23. //    typedef uint32_t digit_type;
  24.     typedef uint64_t double_digit_type; // for multiplication
  25.  
  26.     //const static uint32_t kBase_ = static_cast<digit_type>(pow(10, baseLog_));  // base of numeral system
  27.     const static uint64_t kBase_ = 1000000000;
  28.     const static size_t maxReadSize_ = 20010; // for reading (buffer size), максимальное количество символов на входе
  29.  
  30.     digit_type digits_[maxLength_] = {}; //         должен был обнулиться
  31.     //bool is_negative_;
  32.  
  33.     size_t Length_ = 0;
  34.  
  35. public:
  36.     BigInteger() = default;
  37.     BigInteger(int N) {                      //  только для положительных, про отрицательные не думал
  38.         this->Length_ = ConvertToBase(digits_, N, kBase_);
  39.     }
  40.     BigInteger(const uint64_t N) {                      //  только для положительных, про отрицательные не думал
  41.         this->Length_ = ConvertToBase(digits_, N, kBase_);
  42.     }
  43.     BigInteger(const char* ChN) {               //  только для положительных, про отрицательные не думал
  44.         long long int ind = strlen(ChN);
  45.         char category[baseLog_+1];
  46.         size_t L = 0;
  47.         while (ind > baseLog_) {
  48.             ind -= baseLog_;
  49.             for (long long int i = ind; i < ind + baseLog_; ++i) {
  50.                 category[i - ind] = ChN[i];
  51.             }
  52.             category[baseLog_] = '\0';
  53.             digits_[L++] = atoi(category);
  54.         }
  55.  
  56.         for (long long int i = 0; i < ind; ++i) {
  57.             category[i] = ChN[i];
  58.         }
  59.         if (ind == 1 && category[0] == '0') { // раньше у нуля была длина 1, теперь 0
  60.             Length_ = 0;
  61.         } else {
  62.             category[ind] = '\0';
  63.             digits_[L++] = atoi(category);
  64.             Length_ = L;
  65.         }
  66.     }
  67.  
  68.     friend bool operator==(const BigInteger& lhs, const BigInteger& rhs);
  69.     friend bool operator!=(const BigInteger& lhs, const BigInteger& rhs);
  70.     friend bool operator<(const BigInteger& lhs, const BigInteger& rhs);
  71.     friend bool operator>(const BigInteger& lhs, const BigInteger& rhs);
  72.     friend bool operator>=(const BigInteger& lhs, const BigInteger& rhs);
  73.     friend bool operator<=(const BigInteger& lhs, const BigInteger& rhs);
  74.  
  75.  
  76.     friend BigInteger operator+(const BigInteger& lhs, const BigInteger& rhs);
  77.     friend BigInteger operator-(const BigInteger& lhs, const BigInteger& rhs);
  78.     friend BigInteger operator*(const BigInteger& lhs, const BigInteger& rhs);
  79.     friend BigInteger operator/(const BigInteger& lhs, const BigInteger& rhs);
  80.     friend uint64_t divide_binary_search(const BigInteger& residual, const BigInteger& rhs);
  81.  
  82.     friend istream& operator>>(istream& is, BigInteger& N);
  83.     friend ostream& operator<<(ostream& os, BigInteger N);
  84.  
  85.     BigInteger sqrt() { // не работает почему-то
  86.         BigInteger l(1);
  87.         BigInteger r(*this);
  88.         while (r - l > 1) {
  89.          //   cout << "l = " << l << "       r = " << r << '\n';
  90. //            cout << (l + r) << endl;
  91. //            cout << ((l + r) / (BigInteger)2);
  92.             BigInteger m = ((l + r) / 2);
  93.             BigInteger comparison = m * m;
  94.        //     cout << "m = " << m  << "      m^2 = " << comparison << '\n';
  95.             if (comparison > (*this)) {
  96.                 r = m;
  97.      //       cout << " r = " << r << '\n';
  98.             } else if (comparison < (*this)) {
  99.                 l = m;
  100.    //         cout << " l = " << l << '\n';
  101.             } else {
  102.                 return m;
  103.             }
  104.  //           cout << "----------------------------------------\n";
  105.         }
  106.         return l;
  107.     }
  108. };
  109.  
  110.  
  111.  
  112. size_t ConvertToBase(digit_type* arrN, digit_type N, digit_type kBase) { //           CHECK!
  113.     digit_type L = 0;
  114.     while (N) {
  115.         arrN[L++] = N % kBase;
  116.         N /= kBase;
  117.     }
  118.     return L;
  119. }
  120.  
  121. BigInteger sqrt_binary_search(const BigInteger& BI) {
  122.     BigInteger l = 0;
  123.     BigInteger r = BI;
  124.     while (r - l > 1) {
  125.         BigInteger m = (l + r) / 2;
  126.         BigInteger comparison = m * m;
  127. //        cout << "comparison = " << comparison  << "      residual = " << residual << '\n';
  128.         if (comparison > BI) {
  129.             r = m;
  130. //            cout << " r = " << r << '\n';
  131.         } else if (comparison < BI) {
  132.             l = m;
  133. //            cout << " l = " << r << '\n';
  134.         } else {
  135.             return m;
  136.         }
  137.     }
  138.     return l;
  139. }
  140.  
  141. uint64_t divide_binary_search(const BigInteger& residual, const BigInteger& rhs) {
  142.     uint64_t l = 0, r = residual.kBase_;
  143.     while (r - l > 1) {
  144.         uint64_t m = (l + r) / 2;
  145.         BigInteger comparison = m * rhs;
  146. //        cout << "comparison = " << comparison  << "      residual = " << residual << '\n';
  147.         if (comparison > residual) {
  148.             r = m;
  149. //            cout << " r = " << r << '\n';
  150.         } else if (comparison < residual) {
  151.             l = m;
  152. //            cout << " l = " << r << '\n';
  153.         } else {
  154.             return m;
  155.         }
  156.     }
  157. //    cout << "result_l = " << l << '\n';
  158.     return l;
  159. }
  160.  
  161. bool operator==(const BigInteger& lhs, const BigInteger& rhs) {
  162.     if (lhs.Length_ != rhs.Length_) {
  163.         return false;
  164.     } else {
  165.         for (int i = lhs.Length_; i >= 0; --i) {
  166.             if (lhs.digits_[i] != rhs.digits_[i]) {
  167.                 return false;
  168.             }
  169.         }
  170.         return true;
  171.     }
  172. }
  173. bool operator!=(const BigInteger& lhs, const BigInteger& rhs) {
  174.     return !(lhs == rhs);
  175. }
  176. bool operator<(const BigInteger& lhs, const BigInteger& rhs) {
  177.     if (lhs.Length_ < rhs.Length_) {
  178.         return true;
  179.     } else if (lhs.Length_ > rhs.Length_) {
  180.         return false;
  181.     } else {
  182.         for (int i = lhs.Length_-1; i >= 0; --i) {
  183.             if (lhs.digits_[i] > rhs.digits_[i]) {
  184.                 return false;
  185.             } else if (lhs.digits_[i] < rhs.digits_[i]) {
  186.                 return true;
  187.             }
  188.         }
  189.         return false;
  190.     }
  191. }
  192. bool operator>(const BigInteger& lhs, const BigInteger& rhs) {
  193.     return (!(lhs < rhs) && lhs != rhs);
  194. }
  195. bool operator>=(const BigInteger& lhs, const BigInteger& rhs) {
  196.     return !(lhs < rhs);
  197. }
  198. bool operator<=(const BigInteger& lhs, const BigInteger& rhs) {
  199.     return !(lhs > rhs);
  200. }
  201.  
  202.  
  203.  
  204. BigInteger operator+(const BigInteger& lhs, const BigInteger& rhs) {
  205.     BigInteger res;
  206.     digit_type residual = 0;
  207.     size_t L = max(lhs.Length_, rhs.Length_);
  208.     res.Length_ = L;
  209.     for (size_t i = 0; i < L; ++i) {
  210.         size_t sum = lhs.digits_[i] + rhs.digits_[i] + residual;
  211.         res.digits_[i] = sum % res.kBase_;
  212.         residual = sum / res.kBase_;
  213.     }
  214.     if (residual != 0) {
  215.         res.Length_ = L+1;
  216.         res.digits_[L] = residual;
  217.     }
  218.     return res;
  219. }
  220. BigInteger& operator+=(BigInteger& lhs, const BigInteger& rhs) {
  221.     lhs = lhs + rhs;
  222.     return lhs;
  223. } // не по заданию
  224.  
  225. BigInteger operator-(const BigInteger& lhs, const BigInteger& rhs) {
  226.     BigInteger res = lhs;
  227.     size_t L = lhs.Length_;
  228.     for (size_t i = 0; i < L; ++i) {
  229.         if (res.digits_[i] < rhs.digits_[i]) {
  230.             int borrow = i+1;
  231.             while (res.digits_[borrow] == 0) {
  232.                 res.digits_[borrow] = res.kBase_-1;
  233.                 borrow++;
  234.             }
  235.             --res.digits_[borrow];
  236.             res.digits_[i] += res.kBase_;
  237.         }
  238.         res.digits_[i] -= rhs.digits_[i];
  239.     }
  240.     for (long long int i = L-1; i >=0; --i) {
  241.         if (res.digits_[i] != 0) {
  242.             res.Length_ = i+1;
  243.             return res;
  244.         }
  245.     }
  246.     res.Length_ = 0;
  247.     return res;
  248. }
  249. BigInteger& operator-=(BigInteger& lhs, const BigInteger& rhs) {
  250.     lhs = lhs - rhs;
  251.     return lhs;
  252. } // не по заданию
  253.  
  254. BigInteger operator*(const BigInteger& lhs, const BigInteger& rhs) {
  255.     if (lhs.Length_ == 0 || rhs.Length_ == 0) {
  256.         return 0;
  257.     }
  258.     BigInteger res;
  259.     size_t lenLHS = lhs.Length_;
  260.     size_t lenRHS = rhs.Length_;
  261.     size_t residual = 0;
  262.     for (size_t i = 0; i < lenLHS; ++i) {
  263.         BigInteger help;
  264.         for (size_t j = 0; j < lenRHS; ++j) {
  265.             size_t multiplication = lhs.digits_[i] * rhs.digits_[j] + residual;
  266.             help.digits_[i+j] = multiplication % res.kBase_;
  267.             residual = multiplication / res.kBase_;
  268.         }
  269.         help.Length_ = i + lenRHS;
  270.         if (residual != 0) {
  271.             help.digits_[i + lenRHS] = residual;
  272.             ++help.Length_;
  273.         }
  274.         residual = 0;
  275.         res += help;
  276.     }
  277.     return res;
  278. }
  279. BigInteger& operator*=(BigInteger& lhs, const BigInteger& rhs) {
  280.     lhs = lhs * rhs;
  281.     return lhs;
  282. } // не по заданию
  283.  
  284. BigInteger operator/(const BigInteger& lhs, const BigInteger& rhs) {
  285.     if (lhs < rhs) {
  286.         return 0;
  287.     } else if (lhs == rhs) {
  288.         return 1;
  289.     }
  290.     uint64_t res[lhs.maxLength_];
  291.     int res_ind = 0;
  292.     BigInteger residual;
  293.     int lhs_ind = lhs.Length_ - rhs.Length_;
  294. //    cout << "lhs_ind = " << lhs_ind << '\n';
  295. //    cout << "lhs.Length_ = " << lhs.Length_ << '\n';
  296.  
  297.     // создаем residual
  298.     for (size_t j = 0, i = lhs_ind; i < lhs.Length_; ++i, ++j) {
  299.         residual.digits_[j] = lhs.digits_[i];
  300.         ++residual.Length_;
  301.     }
  302. //    cout << residual << '\n';
  303.  
  304.     if (residual < rhs) {
  305.         residual = (residual * residual.kBase_ + lhs.digits_[--lhs_ind]);
  306.     }//                                                                 теперь residual точно больше rhs
  307.  
  308.     for (; lhs_ind >= 0;) {
  309.  
  310.         if (residual < rhs) {
  311. //            residual = (residual * residual.kBase_ + lhs.digits_[lhs_ind]);
  312.             res[res_ind++] = 0;
  313.         } else {
  314.  
  315.     //    if (residual >= rhs) { // ????????????????????????????????????
  316. //            cout << residual << '\n';
  317.  
  318.             res[res_ind] = divide_binary_search(residual, rhs);
  319.             residual = (residual - rhs * res[res_ind++]); // остаток
  320.  
  321. //            cout << residual << '\n';
  322.         }
  323.         residual = (residual * residual.kBase_ + lhs.digits_[--lhs_ind]);
  324.     }
  325. //    cout << res_ind << '\n';
  326.     BigInteger BIres;
  327.     for (int i = res_ind-1, j = 0; i >=0; --i, ++j) {
  328.         BIres.digits_[j] = res[i];
  329.         ++BIres.Length_;
  330.     }
  331.  
  332.     return BIres;
  333. }
  334. BigInteger& operator/=(BigInteger& lhs, const BigInteger& rhs) {
  335.     lhs = lhs / rhs;
  336.     return lhs;
  337. } // не по заданию
  338.  
  339. BigInteger operator%(const BigInteger& lhs, const BigInteger& rhs) {
  340.     return lhs - rhs * (lhs/rhs);
  341. }
  342. BigInteger& operator%=(BigInteger& lhs, const BigInteger& rhs) {
  343.     lhs = lhs % rhs;
  344.     return lhs;
  345. } // не по заданию
  346.  
  347.  
  348.  
  349.  
  350.  
  351. BigInteger NOD(BigInteger p, BigInteger q) {
  352.     while (q != 0) {
  353.         p %= q;
  354.         swap(p, q);
  355.     }
  356.     return p;
  357. }
  358.  
  359. istream& operator>>(istream& is, BigInteger& N) {
  360.     char N_ch[N.maxReadSize_+1];
  361.     is >> N_ch;
  362.     N_ch[N.maxReadSize_] = '\0';
  363.     N = BigInteger(N_ch);
  364.     return is;
  365. }
  366. ostream& operator<<(ostream& os, BigInteger N) {
  367.     if (N.Length_==0) {
  368.         os << 0;
  369.     } else {
  370. /*
  371.         if (!true) {
  372.             os << '-';
  373.         }
  374. */
  375.         os << N.digits_[N.Length_-1];
  376.         for (long long int i = N.Length_-2; i >= 0 ; --i) {
  377.             os<< setfill('0') << setw(N.baseLog_) << N.digits_[i]; //                   зависиит от kBase!
  378.         }
  379.     }
  380.     return os;
  381. }
  382.  
  383. int main() {
  384. //    std::ios_base::sync_with_stdio(false); // отключает синхронизацию iostreams с stdio
  385. //    std::cin.tie(nullptr);
  386. /*
  387.     BigInteger b("123");
  388.     BigInteger c(91);
  389.     BigInteger d;
  390.     d = b+c;
  391.     cout <<setw(2)<< d << '\n';
  392.     cout << 1234124134;
  393. */
  394.  
  395.  //   cout << (BigInteger(201) / (BigInteger)(2)) << endl;
  396.     BigInteger A;
  397.     BigInteger B;
  398.     std::cin >> A >> B;
  399.  
  400.     cout << A/B << ' ' <<A%B;
  401.  
  402. /*
  403.     BigInteger a, b;
  404.     std::cin >> a >> b;
  405.     int c;
  406.     std::cin >> c;
  407.  
  408.     std::cout << (a * c == c * --b++) << '\n';
  409.     std::cout << (a + 5 < ++b--) << '\n';
  410.     std::cout << (a <= b) << '\n';
  411.     std::cout << (a > b - 5) << '\n';
  412.     std::cout << (a >= b - 5) << '\n';
  413.     std::cout << (a != b * c) << '\n';
  414.     std::cout << (a == -b) << '\n';
  415.  
  416.     BigInteger d("123"), e(1ULL << 63);
  417.     std::cout << (d + c) * e << '\n';
  418.  
  419.     try {
  420.         a += b;
  421.         b = a - b;
  422.         a -= b;
  423.         std::cout << a + b << '\n';
  424.         std::cout << a - b << '\n';
  425.         std::cout << a * b << '\n';
  426.     } catch (BigIntegerOverflow) {
  427.         std::cout << "Overflow" << '\n';
  428.     }
  429. */
  430. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement