Advertisement
0andrejj0

Untitled

Dec 8th, 2022
399
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 13.83 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <cstring>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <deque>
  7.  
  8. class BigInteger {
  9. private:
  10.     static const int64_t basePow = 9;
  11.     static const int64_t base = 1'000'000'000;
  12.  
  13. private:
  14.  
  15.    bool sign;
  16.    std::deque<int64_t> data;
  17.  
  18. private:
  19.    static void add(BigInteger& a, const BigInteger& b) {
  20.        a.data.resize(std::max(b.data.size(), a.data.size()) + 2);
  21.        for (size_t i = 0; i < b.data.size(); ++i) {
  22.            a.data[i] += b.data[i];
  23.        }
  24.        for (size_t i = 0; i < a.data.size(); ++i) {
  25.            if (i > b.data.size() && a.data[i] < base)
  26.                break;
  27.            if (a.data[i] >= base) {
  28.                a.data[i + 1] += a.data[i] / base;
  29.                a.data[i] %= base;
  30.            }
  31.        }
  32.        while (!a.data.empty() && a.data.back() == 0)
  33.            a.data.pop_back();
  34.    }
  35.  
  36.    static void sub(BigInteger& a, const BigInteger& b) {
  37.        for (size_t i = 0; i < b.data.size(); ++i) {
  38.            a.data[i] -= b.data[i];
  39.        }
  40.        for (size_t i = 0; i < a.data.size(); ++i) {
  41.            if (i > b.data.size() && a.data[i] > 0)
  42.                break;
  43.            if (a.data[i] < 0) {
  44.                a.data[i] += base;
  45.                --a.data[i + 1];
  46.            }
  47.        }
  48.        while (!a.data.empty() && a.data.back() == 0)
  49.            a.data.pop_back();
  50.    }
  51.  
  52. public:
  53.    BigInteger() : sign(true) {}
  54.  
  55.    BigInteger(int n) {
  56.        if (n < 0) {
  57.            sign = false;
  58.            n = -n;
  59.        } else {
  60.            sign = true;
  61.        }
  62.        while (n) {
  63.            data.push_back(n % base);
  64.            n /= base;
  65.        }
  66.    }
  67.  
  68.    explicit BigInteger(const char* s) {
  69.        if (s[0] == '-') {
  70.            sign = false;
  71.            ++s;
  72.        } else {
  73.            sign = true;
  74.        }
  75.  
  76.        size_t len = strlen(s);
  77.        data.resize(len / basePow + (len % basePow > 0));
  78.        size_t pw = 1;
  79.        size_t block = 0;
  80.        for (auto it = s + len - 1; it >= s; --it) {
  81.            data[block] += (*it - '0') * pw;
  82.            pw *= 10;
  83.            if (pw == base) {
  84.                pw = 1;
  85.                ++block;
  86.            }
  87.        }
  88.        while (!data.empty() && data.back() == 0)
  89.            data.pop_back();
  90.        if (data.empty())
  91.            sign = true;
  92.    }
  93.  
  94.    BigInteger(const BigInteger& oth) {
  95.        sign = oth.sign;
  96.        data = oth.data;
  97.    }
  98.  
  99.    bool iszero() {
  100.        return data.empty();
  101.    }
  102.  
  103.    static std::pair<BigInteger, BigInteger> divMod(const BigInteger& a, const BigInteger& b) {
  104.        std::pair<BigInteger, BigInteger> res;
  105.        if (cmpAbs(a, b))
  106.            return {0, a};
  107.        BigInteger cur;
  108.        auto it = a.data.rbegin();
  109.        while (cmpAbs(cur, b)) {
  110.            cur.data.push_front(*it);
  111.            ++it;
  112.        }
  113.        std::vector<int64_t> ans;
  114.        while (it != a.data.rend() + 1) {
  115.            int64_t l = 0, r = base;
  116.            while (r - l > 1) {
  117.                int64_t m = (l + r) / 2;
  118.                auto s = b;
  119.                s *= BigInteger(m);
  120.                if (cmpAbs(cur, s))
  121.                    r = m;
  122.                else
  123.                    l = m;
  124.            }
  125.            BigInteger delta = BigInteger(l);
  126.            delta *= BigInteger(b);
  127.            if (b.sign) {
  128.                cur -= delta;
  129.            } else {
  130.                cur += delta;
  131.            }
  132.            ans.push_back(l);
  133.            if (it != a.data.rend())
  134.                cur.data.push_front(*it);
  135.            ++it;
  136.        }
  137.        for (auto i = ans.rbegin(); i != ans.rend(); ++i)
  138.            res.first.data.push_back(*i);
  139.        res.second = cur;
  140.        while (!res.first.data.empty() && res.first.data.back() == 0)
  141.            res.first.data.pop_back();
  142.        while (!res.second.data.empty() && res.second.data.back() == 0)
  143.            res.second.data.pop_back();
  144.        return res;
  145.    }
  146.  
  147.    static bool cmpAbs(const BigInteger& a, const BigInteger& b) {
  148.        if (a.data.size() != b.data.size()) {
  149.            return a.data.size() < b.data.size();
  150.        } else {
  151.            for (int64_t i = static_cast<int64_t>(a.data.size()) - 1; i >= 0; --i) {
  152.                if (a.data[i] != b.data[i])
  153.                    return a.data[i] < b.data[i];
  154.            }
  155.        }
  156.        return false;
  157.    }
  158.  
  159. public:
  160.    std::string toString() const {
  161.        if (data.empty())
  162.            return "0";
  163.        std::string res;
  164.        std::string cur;
  165.        if (!sign)
  166.            res += '-';
  167.        res.reserve(9 * data.size());
  168.        for (auto it = data.rbegin(); it != data.rend(); ++it) {
  169.            cur = std::to_string(*it);
  170.            if (!res.empty() && res != "-")
  171.                while (cur.size() < basePow) {
  172.                    cur = "0" + cur;
  173.                }
  174.            res += cur;
  175.        }
  176.        if (res == "-0")
  177.            return "0";
  178.        return res;
  179.    }
  180.  
  181.    std::string to_string() const {
  182.        if (data.empty())
  183.            return "0";
  184.        std::string res;
  185.        std::string cur;
  186.        if (!sign)
  187.            res += '-';
  188.        res.reserve(9 * data.size());
  189.        for (auto it = data.rbegin(); it != data.rend(); ++it) {
  190.            cur = std::to_string(*it);
  191.            if (!res.empty() && res != "-")
  192.                while (cur.size() < basePow) {
  193.                    cur = "0" + cur;
  194.                }
  195.            res += cur;
  196.        }
  197.        if (res == "-0")
  198.            return "0";
  199.        return res;
  200.    }
  201.  
  202.    BigInteger& operator+=(const BigInteger& oth) {
  203.        if (sign == oth.sign)
  204.            add(*this, oth);
  205.        else {
  206.            if (cmpAbs(*this, oth)) {
  207.                BigInteger copy = oth;
  208.                sub(copy, *this);
  209.                *this = copy;
  210.            } else {
  211.                sub(*this, oth);
  212.            }
  213.        }
  214.        if (data.empty())
  215.            sign = true;
  216.        return *this;
  217.    }
  218.  
  219.    BigInteger& operator-=(const BigInteger& oth) {
  220.        *this += (-oth);
  221.        return *this;
  222.    }
  223.  
  224.    BigInteger& operator=(const BigInteger& oth) {
  225.        data = oth.data;
  226.        sign = oth.sign;
  227.        return *this;
  228.    }
  229.  
  230.    bool getSign() const {
  231.        return sign;
  232.    }
  233.  
  234.    void flipSign() {
  235.        sign = !sign;
  236.    }
  237.  
  238.    explicit operator bool() const {
  239.        return !data.empty();
  240.    }
  241.  
  242.    BigInteger& operator*=(const BigInteger& oth) {
  243.        auto len = data.size() + oth.data.size() + 2;
  244.        BigInteger res;
  245.        res.data.resize(len);
  246.        for (size_t i = 0; i < data.size(); ++i) {
  247.            for (size_t j = 0; j < oth.data.size(); ++j) {
  248.                res.data[i + j] += data[i] * oth.data[j];
  249.                if (res.data[i + j] >= base) {
  250.                    res.data[i + j + 1] += res.data[i + j] / base;
  251.                    res.data[i + j] %= base;
  252.                }
  253.            }
  254.        }
  255.        for (size_t i = 0; i < res.data.size(); ++i)
  256.            if (res.data[i] >= base) {
  257.                res.data[i + 1] += res.data[i] / base;
  258.                res.data[i] %= base;
  259.            }
  260.        while (!res.data.empty() && res.data.back() == 0)
  261.            res.data.pop_back();
  262.        res.sign = (sign == oth.sign);
  263.        *this = res;
  264.        return *this;
  265.    }
  266.  
  267.    BigInteger operator-() const {
  268.        BigInteger res = *this;
  269.        res.flipSign();
  270.        return res;
  271.    }
  272.  
  273.    BigInteger operator+() const {
  274.        return *this;
  275.    }
  276.  
  277.    BigInteger& operator++() {
  278.        *this += BigInteger(1);
  279.        return *this;
  280.    }
  281.  
  282.    const BigInteger operator++(int) {
  283.        BigInteger old = *this;
  284.        *this += BigInteger(1);
  285.        return old;
  286.    }
  287.  
  288.    BigInteger& operator--() {
  289.        *this += BigInteger(-1);
  290.        return *this;
  291.    }
  292.  
  293.    const BigInteger operator--(int) {
  294.        BigInteger old = *this;
  295.        *this += BigInteger(-1);
  296.        return old;
  297.    }
  298.  
  299.    BigInteger& operator/=(const BigInteger& oth) {
  300.        auto newSign = (sign == oth.sign);
  301.        *this = divMod(*this, oth).first;
  302.        sign = newSign;
  303.        return *this;
  304.    }
  305.  
  306.    BigInteger& operator%=(const BigInteger& oth) {
  307.        auto newSign = (sign == oth.sign);
  308.        *this = divMod(*this, oth).second;
  309.        sign = newSign;
  310.        return *this;
  311.    }
  312.  
  313. public:
  314.    static BigInteger gcd(BigInteger a, BigInteger b) {
  315.        while (b) {
  316.            a %= b;
  317.            std::swap(a, b);
  318.        }
  319.        return a;
  320.    }
  321. };
  322.  
  323. BigInteger operator+(const BigInteger& a, const BigInteger& b) {
  324.    BigInteger res = a;
  325.    res += b;
  326.    return res;
  327. }
  328.  
  329. BigInteger operator-(const BigInteger& a, const BigInteger& b) {
  330.    BigInteger res = a;
  331.    res -= b;
  332.    return res;
  333. }
  334.  
  335. BigInteger operator/(const BigInteger& a, const BigInteger& b) {
  336.    BigInteger res = a;
  337.    res /= b;
  338.    return res;
  339. }
  340.  
  341. BigInteger operator%(const BigInteger& a, const BigInteger& b) {
  342.    BigInteger res = a;
  343.    res %= b;
  344.    return res;
  345. }
  346.  
  347. BigInteger operator*(const BigInteger& a, const BigInteger& b) {
  348.    BigInteger res = a;
  349.    res *= b;
  350.    return res;
  351. }
  352.  
  353. std::ostream& operator<<(std::ostream& out, const BigInteger& a) {
  354.    out << a.toString();
  355.    return out;
  356. }
  357.  
  358. std::istream& operator>>(std::istream& in, BigInteger& a) {
  359.    std::string s;
  360.    in >> s;
  361.    a = BigInteger(s.c_str());
  362.    return in;
  363. }
  364.  
  365.  
  366. bool operator<(const BigInteger& a, const BigInteger& b) {
  367.    BigInteger tmp = b - a;
  368.    return tmp.getSign() && !tmp.iszero();
  369. }
  370.  
  371. bool operator>(const BigInteger& a, const BigInteger& b) {
  372.    return b < a;
  373. }
  374.  
  375. bool operator==(const BigInteger& a, const BigInteger& b) {
  376.    return (a - b).iszero();
  377. }
  378.  
  379. bool operator!=(const BigInteger& a, const BigInteger& b) {
  380.    return !(a == b);
  381. }
  382.  
  383. bool operator<=(const BigInteger& a, const BigInteger& b) {
  384.    BigInteger tmp = b - a;
  385.    return tmp.getSign();
  386. }
  387.  
  388. bool operator>=(const BigInteger& a, const BigInteger& b) {
  389.    return b <= a;
  390. }
  391.  
  392.  
  393. class Rational {
  394. public:
  395.    BigInteger c;
  396.    BigInteger z;
  397.  
  398.    Rational(int n = 0) : c(n), z(1) {}
  399.  
  400.    Rational(const BigInteger& n) : c(n), z(1) {}
  401.  
  402.    Rational(const Rational& oth) {
  403.        *this = oth;
  404.    }
  405.  
  406.    void normalize() {
  407.        BigInteger div = BigInteger::gcd(c, z);
  408.        if (div) {
  409.            c /= div;
  410.            z /= div;
  411.        }
  412.        if (!z.getSign()) {
  413.            c.flipSign();
  414.            z.flipSign();
  415.        }
  416.    }
  417.  
  418.    Rational& operator=(const Rational& oth) = default;
  419.  
  420.    Rational(const BigInteger& a, const BigInteger& b) : c(a), z(b) {
  421.        normalize();
  422.    }
  423.  
  424.    Rational& operator*=(const Rational& oth) {
  425.        c *= oth.c;
  426.        z *= oth.z;
  427.        normalize();
  428.        return *this;
  429.    }
  430.  
  431.    Rational& operator/=(const Rational& oth) {
  432.        c *= oth.z;
  433.        z *= oth.c;
  434.        normalize();
  435.        return *this;
  436.    }
  437.  
  438.    Rational& operator+=(const Rational& oth) {
  439.        c = c * oth.z + oth.c * z;
  440.        z *= oth.z;
  441.        normalize();
  442.        return *this;
  443.    }
  444.  
  445.    Rational& operator-=(const Rational& oth) {
  446.        c = c * oth.z - oth.c * z;
  447.        z *= oth.z;
  448.        normalize();
  449.        return *this;
  450.    }
  451.  
  452.    Rational operator-() {
  453.        Rational res = *this;
  454.        res.c.flipSign();
  455.        return res;
  456.    }
  457.  
  458.    std::string toString() const {
  459.        std::string res;
  460.        res += c.toString();
  461.        if (z != 1) {
  462.            res += '/';
  463.            res += z.toString();
  464.        }
  465.        return res;
  466.    }
  467.  
  468.    std::string asDecimal(size_t precision = 0) const {
  469.        std::string res;
  470.        if (c == 0) {
  471.            return "0";
  472.        }
  473.        if (!c.getSign())
  474.            res += '-';
  475.        auto dm = BigInteger::divMod(c, z);
  476.        res += dm.first.toString();
  477.        if (precision == 0)
  478.            return res;
  479.        res += '.';
  480.        size_t needSize = res.size() + precision;
  481.        auto cur = dm.second * 1'000'000'000;
  482.         if (!cur.getSign())
  483.             cur.flipSign();
  484.         while (res.size() < needSize) {
  485.             auto currentStr = (cur / z).toString();
  486.             cur = (cur % z) * 1'000'000'000;
  487.            while (currentStr.size() < 9)
  488.                currentStr = "0" + currentStr;
  489.            res += currentStr;
  490.        }
  491.        while (res.size() > needSize)
  492.            res.pop_back();
  493.        return res;
  494.    }
  495. };
  496.  
  497. Rational operator+(const Rational& a, const Rational& b) {
  498.    Rational res = a;
  499.    res += b;
  500.    res.normalize();
  501.    return res;
  502. }
  503.  
  504. Rational operator-(const Rational& a, const Rational& b) {
  505.    Rational res = a;
  506.    res -= b;
  507.    res.normalize();
  508.    return res;
  509. }
  510.  
  511. Rational operator*(const Rational& a, const Rational& b) {
  512.    Rational res = a;
  513.    res *= b;
  514.    res.normalize();
  515.    return res;
  516. }
  517.  
  518. Rational operator/(const Rational& a, const Rational& b) {
  519.    Rational res = a;
  520.    res /= b;
  521.    res.normalize();
  522.    return res;
  523. }
  524.  
  525. bool operator==(const Rational& a, const Rational& b) {
  526.    return a.c == b.c && a.z == b.z;
  527. }
  528.  
  529. bool operator!=(const Rational& a, const Rational& b) {
  530.    return a.c != b.c || a.z != b.z;
  531. }
  532.  
  533. bool operator<(const Rational& a, const Rational& b) {
  534.    if (a.c.getSign()) {
  535.        if (b.c.getSign())
  536.            return a.c * b.z < a.z * b.c;
  537.        else {
  538.            return false;
  539.        }
  540.    } else {
  541.        if (b.c.getSign())
  542.            return true;
  543.        else {
  544.            return a.c * b.z < a.z * b.c;
  545.        }
  546.    }
  547. }
  548.  
  549. bool operator>(const Rational& a, const Rational& b) {
  550.    return b < a;
  551. }
  552.  
  553. bool operator>=(const Rational& a, const Rational& b) {
  554.    return b < a || b == a;
  555. }
  556.  
  557. bool operator<=(const Rational& a, const Rational& b) {
  558.    return a < b || b == a;
  559. }
  560.  
  561. using bigint=BigInteger;
  562.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement