Advertisement
KShah

Untitled

Nov 24th, 2021
854
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 23.81 KB | None | 0 0
  1. #include<vector>
  2. #include<iostream>
  3. #include<string>
  4. #define $$ std::cout << "------------\n";
  5. //#define print(s) std::cout << "print:\n  ";for(auto qwe:s) std::cout << qwe << ' '; std::cout << '\n';
  6. class BigInteger{
  7.     private:
  8.         std::vector<int> deg;
  9.         int sign = 1;
  10.         int size(){
  11.             return static_cast<int>(deg.size());
  12.         }
  13.         void Normalize(){
  14.             //print(deg)
  15.             int more = 0;
  16.             for(size_t i = 0; i < deg.size(); ++i){
  17.                 deg[i] += more;
  18.                 if (deg[i] >= 0) {
  19.                     more = deg[i] / 10;
  20.                 }else{
  21.                     more = -1;
  22.                 }
  23.                 deg[i] = (deg[i] + 10) % 10;
  24.             }
  25.             while(more){
  26.                 deg.push_back(more % 10);
  27.                 more /= 10;
  28.             }
  29.             while(deg.size() > 1 && deg.back() == 0){
  30.                 deg.pop_back();
  31.             }
  32.             if(!*this){
  33.                 sign = 1;
  34.             }
  35.         }
  36.         void reverse(){
  37.             for(size_t i = 0; i < deg.size() / 2; ++i){
  38.                 std::swap(deg[i], deg[deg.size() - i - 1]);
  39.             }
  40.         }
  41.  
  42.  
  43.     public:
  44.         BigInteger(const BigInteger &other){
  45.             sign = other.sign;
  46.             deg.resize(other.deg.size());
  47.             for(size_t i = 0; i < other.deg.size(); ++i){
  48.                 deg[i] = other.deg[i];
  49.             }
  50.         }
  51.         BigInteger(const std::string &s){
  52.             size_t i = 0;
  53.             if(s[i] == '-'){
  54.                 sign = -1;
  55.                 i++;
  56.             }else{
  57.                 sign = 1;
  58.             }
  59.             deg.resize(s.size() - i);
  60.             for(; i < s.size(); ++i){
  61.                  //   std::cout << i << ' ' << s.size() - i - 1 << '\n';
  62.                 int ch = sign == -1 ? s[s.size() - i] : s[s.size() - i - 1];
  63.                 if(sign == -1){
  64.                     deg[i - 1] = ch - '0';
  65.                 }else{
  66.                     deg[i] = ch - '0';
  67.                 }
  68.             }
  69.             //std::cout << "*********\n" << s << '\n';
  70.             //for(auto i: deg) std::cout << i << ' ';
  71.             //std::cout << '\n';
  72.         }
  73.         BigInteger(){
  74.             sign = 1;
  75.             deg = {0};
  76.         }
  77.         BigInteger(int num){
  78.             //std::cout << "******\n";
  79.             //std::cout << sign << ' ' << deg.size() << '\n';
  80.             if(num < 0){
  81.                 sign = -1;
  82.                 num *= -1;
  83.             }else{
  84.                 sign = 1;
  85.             }
  86.             while(num){
  87.                 int rem = num % 10;
  88.                 num /= 10;
  89.                 deg.push_back(rem);
  90.             }
  91.             if(deg.empty()){
  92.                 deg = {0};
  93.             }
  94.             //std::cout << sign << ' ' << deg.size() << ' ' << deg[0] <<  '\n';
  95.           // std:: cout << "wqeqweqweqw\n";
  96.         }
  97.         BigInteger(int k, int degree){
  98.             //std::cout << "qweqwrt\n";
  99.             deg.assign(degree, 0);
  100.            // std::cout << k << ' ' << degree << '\n';
  101.             deg[deg.size() - 1] = k;
  102.             //$$
  103.         }
  104.         std::string toString() const {
  105.            // print(deg)
  106.             std::string number = "";
  107.             if(sign == -1){
  108.                 number += "-";
  109.             }
  110.             for(int i = static_cast<int>(deg.size()) - 1; i >= 0; --i){
  111.                 number += char('0' + deg[i]);
  112.                 if(i == 0){
  113.                     break;
  114.                 }
  115.             }
  116.             return number;
  117.         }
  118.         friend std::istream& operator>>(std::istream &in, BigInteger &self){
  119.             std::string input;
  120.             in >> input;
  121.             self = BigInteger(input);
  122.             return in;
  123.         }
  124.         friend std::ostream& operator<<(std::ostream &out, const BigInteger& P){
  125.             //print(P.toString());
  126.             out << P.toString();
  127.             return out;
  128.         }
  129.         /*std::string toString(BigInteger &other) const {
  130.             std::string number = "";
  131.             if(other.sign == -1){
  132.                 number += "-";
  133.             }
  134.             for(size_t i = other.deg.size() - 1; i > -1; --i){
  135.                 number += char('0' + deg[i]);
  136.             }
  137.             return number;
  138.         }*/
  139.         BigInteger& operator*=(int mul){
  140.             //if(mul < 0){
  141.               //  sign *= -1;
  142.                // mul *= -1;
  143.             //}
  144.            // std::cout << "000000000000\n";
  145.             //for(int i = 0; i < deg.size(); ++i){
  146.              //       std::cout << deg[i] << '\n';
  147.              //   deg[i] *= mul;
  148.            // std::cout << deg[i] << '\n';
  149.             //}
  150.             //std::cout << "***********   " << *this << '\n';
  151.             *this *= BigInteger(mul);
  152.             return *this;
  153.         }
  154.         BigInteger operator -() const {
  155.             BigInteger ans = *this;
  156.             ans.sign *= -1;
  157.             //sign *= -1;
  158.             return ans;
  159.         }
  160.         BigInteger& operator +=(const BigInteger &other){
  161.             if(sign != other.sign){
  162.                 sign *= -1;
  163.                 *this -= other;
  164.                 sign *= -1;
  165.                 Normalize();
  166.                 return *this;
  167.             }
  168.             const size_t min_size = std::min(deg.size(), other.deg.size());
  169.             for(size_t i = 0; i < min_size; ++i){
  170.                 deg[i] += other.deg[i];
  171.             }
  172.             for(size_t i = min_size; i < other.deg.size(); ++i) {
  173.                 deg.push_back(other.deg[i]);
  174.             }
  175.             Normalize();
  176.             return *this;
  177.         }
  178.         BigInteger& operator -=(const BigInteger &other){
  179.             //$$
  180.             //print(deg)
  181.             //print(other.deg)
  182.         //    std::cout << "  " << sign << ' ' << other.sign << ' ' << *this << ' ' << other << ' ' << (*this < other) << '\n';
  183.             if(sign != other.sign){
  184.                 sign *= -1;
  185.                 *this += other;
  186.                 sign *= -1;
  187.                 Normalize();
  188.                 return *this;
  189.             }
  190.             size_t min_size = std::min(deg.size(), other.deg.size());
  191.             if(SmallerMod(*this, other)){
  192.                 int more = 0;
  193.                 for(size_t i = 0; i < min_size; ++i){
  194.                     if (deg[i] + more <= other.deg[i]) {
  195.                         deg[i] = other.deg[i] - deg[i] - more;
  196.                         more = 0;
  197.                     }else{
  198.                         deg[i] = other.deg[i] - deg[i] - more + 10;
  199.                         more = 1;
  200.                     }
  201.                 }
  202.                // std::cout << "qwerty\n";
  203.                 //print(deg);
  204.                 for(size_t i = min_size; i < other.deg.size(); ++i){
  205.                     deg.push_back(other.deg[i] - more);
  206.                     more = 0;
  207.                 }
  208.                 sign *= -1;
  209.             }else{
  210.                 for(size_t i = 0; i < min_size; ++i){
  211.                     deg[i] -= other.deg[i];
  212.                 }
  213.             }
  214.             //print(deg)
  215.             Normalize();
  216.             //std::cout << "0000000\n";
  217.             //print(deg)
  218.             return *this;
  219.     }
  220.         void operator +=(int add){
  221.  
  222.             *this += BigInteger(add);
  223.         }
  224.         void operator -=(int ded){
  225.             *this -= BigInteger(ded);
  226.         }
  227.         BigInteger operator +(const BigInteger &other) const {
  228.             BigInteger result = *this;
  229.             result += other;
  230.             return result;
  231.         }
  232.         BigInteger operator -(const BigInteger &other) const {
  233.             BigInteger result = *this;
  234.             result -= other;
  235.             return result;
  236.         }
  237.         bool operator ==(const BigInteger &other) const {
  238.             return other.toString() == toString();
  239.         }
  240.         bool operator !=(const BigInteger &other) const {
  241.             return !(*this == other);
  242.         }
  243.         bool operator <(const BigInteger &other) const {
  244.             if(sign < other.sign){
  245.                 return true;
  246.             }else if(sign > other.sign){
  247.                 return false;
  248.             }
  249.            // std::cout << "WWWWWWWWWW\n";
  250.             //std::cout << SmallerMod(*this, other) << ' ' << sign << ' ' << *this << ' ' << other.sign << ' ' << other << '\n';
  251.             return SmallerMod(*this, other) ^ (sign == 1) ^ 1;
  252.         }
  253.         bool operator >(const BigInteger &other) const {
  254.             return (other < *this);
  255.         }
  256.         bool operator >=(const BigInteger &other) const {
  257.             return (*this > other) || (*this == other);
  258.         }
  259.         bool operator <=(const BigInteger &other) const {
  260.             return (*this < other) || (*this == other);
  261.         }
  262.         BigInteger& operator =(const BigInteger& other){
  263.             sign = other.sign;
  264.             deg = other.deg;
  265.             return *this;
  266.         }
  267.         BigInteger& operator =(const int other){
  268.             *this = BigInteger(other);
  269.             return *this;
  270.         }
  271.         BigInteger operator +(const int add) const {
  272.             return *this + BigInteger(add);
  273.         }
  274.         BigInteger operator -(const int ded) const {
  275.             return *this - BigInteger(ded);
  276.         }
  277.         BigInteger operator *(const int other) const {
  278.             return *this * BigInteger(other);
  279.         }
  280.         bool operator ==(const int other) const {
  281.             return *this == BigInteger(other);
  282.         }
  283.         bool operator !=(const int other) const {
  284.             return *this != BigInteger(other);
  285.         }
  286.         bool operator <(const int other) const {
  287.             return *this < BigInteger(other);
  288.         }
  289.         bool operator <=(const int other) const {
  290.             return *this <= BigInteger(other);
  291.         }
  292.         bool operator >(const int other) const {
  293.             return *this > BigInteger(other);
  294.         }
  295.         bool operator >=(const int other) const {
  296.             return *this >= BigInteger(other);
  297.         }
  298.         BigInteger& operator++(){
  299.             *this += 1;
  300.             return *this;
  301.         }
  302.         BigInteger& operator--(){
  303.             *this -= 1;
  304.             return *this;
  305.         }
  306.         BigInteger operator++(int) {
  307.             BigInteger old = *this;
  308.             *this += 1;
  309.             return old;
  310.         }
  311.         BigInteger operator--(int) {
  312.             BigInteger old = *this;
  313.             *this -= 1;
  314.             return old;
  315.         }
  316.         friend BigInteger operator +(const int self, const BigInteger& other){
  317.             return BigInteger(self) + other;
  318.         }
  319.         friend BigInteger operator-(const int self, const BigInteger& other){
  320.             return BigInteger(self) - other;
  321.         }
  322.         friend BigInteger operator*(const int self, const BigInteger& other){
  323.            return BigInteger(self) * other;
  324.         }
  325.         friend BigInteger operator/(const int self, const BigInteger& other){
  326.             return BigInteger(self) / other;
  327.         }
  328.         friend BigInteger operator%(const int self, const BigInteger& other){
  329.             return BigInteger(self) % other;
  330.         }
  331.         operator bool() const {
  332.             return deg[0] || deg.size() > 1;
  333.         }
  334.         BigInteger operator *(const BigInteger &other) const {
  335.             BigInteger composition;
  336.             composition.deg.resize(deg.size() + other.deg.size());
  337.             for(size_t i = 0; i < deg.size(); ++i){
  338.                 for(size_t j = 0; j < other.deg.size(); ++j){
  339.                     composition.deg[i + j] += deg[i] * other.deg[j];
  340.                 }
  341.             }
  342.             composition.sign = sign * other.sign;
  343.             composition.Normalize();
  344.             return composition;
  345.         }
  346.         BigInteger& operator *=(const BigInteger &other){
  347.             *this = *this * other;
  348.             return *this;
  349.         }
  350.         /*BigInteger operator /(const BigInteger &other) const {
  351.             BigInteger A = *this, B = other;
  352.             A.sign = 1;
  353.             B.sign = 1;
  354.             BigInteger ans = 0;
  355.             ans.sign = sign * other.sign;
  356.             while(A.deg.size() >= B.deg.size()){
  357.                // std::cout << "   " << A.deg.back() << ' ' << B.deg.back() << std::endl;
  358.                 BigInteger P = BigInteger((A.deg.back() + B.deg.back() - 1 + 1) / B.deg.back(), A.deg.size() - B.deg.size() + 1);
  359.                 ans += P;
  360.                 A -= P * B;
  361.             }
  362.             return ans;
  363.         }*/
  364.         BigInteger operator /(const BigInteger &other) const {
  365.             BigInteger result = *this;
  366.             result /= other;
  367.             return result;
  368.         }
  369.         BigInteger& operator %=(const BigInteger &other){
  370.             *this -= *this / other * other;
  371.             return *this;
  372.         }
  373.         BigInteger operator %(const BigInteger &other) const {
  374.             return *this - other * (*this / other);
  375.         }
  376.         BigInteger& operator /=(const BigInteger &other){
  377.          //   print(deg)
  378.            // print(other.deg)
  379.             if (SmallerMod(*this, other)){
  380.                 *this = 0;
  381.                 return *this;
  382.             }
  383.             sign *= other.sign;
  384.             reverse();
  385.             std::vector<int> new_deg;
  386.             BigInteger val = 0;
  387.             //$$
  388.             for(size_t i = 0; i < deg.size() + 1; ++i) {
  389.                 //print(new_deg)
  390.                 //std::cout << val << '\n';
  391.                 new_deg.push_back(divide_two(val, other));
  392.                 //std::cout << "  " << val << ' ' << new_deg.back() << '\n';
  393.                 val -= other * new_deg.back();
  394.                 if(i == deg.size()){
  395.                     break;
  396.                 }
  397.                 val *= 10;
  398.                 val += deg[i];
  399.             }
  400.             deg = new_deg;
  401.             reverse();
  402.             Normalize();
  403.             return *this;
  404.         }
  405.         int divide_two(const BigInteger &self, const BigInteger &other) {
  406.             for(int i = 0; i < 10; ++i){
  407.                 if (other * (i + 1) > self || -other * (i + 1) > self) {
  408.                     return i;
  409.                 }
  410.             }
  411.             return 0;
  412.         }
  413.         BigInteger operator /(const int other) const {
  414.             return *this / BigInteger(other);
  415.         }
  416.         BigInteger& operator %=(const int other){
  417.             *this %= BigInteger(other);
  418.             return *this;
  419.         }
  420.         BigInteger operator %(const int other) const {
  421.             return *this % BigInteger(other);
  422.         }
  423.         BigInteger& operator /=(const int other){
  424.             *this /= BigInteger(other);
  425.             return *this;
  426.         }
  427.         void change_sign(){
  428.             sign *= -1;
  429.         }
  430.         int get_sign() const {
  431.             return sign;
  432.         }
  433.         friend bool SmallerMod(const BigInteger&, const BigInteger&);
  434. };
  435.  
  436. template<typename T>
  437. T gcd(T a, T b){
  438.     while(b){
  439.         a = a % b;
  440.         std::swap(a, b);
  441.     }
  442.     return a;
  443. }
  444. bool SmallerMod(const BigInteger &self, const BigInteger &other){
  445.     if(self.deg.size() < other.deg.size()){
  446.         return 1;
  447.     }else if(self.deg.size() > other.deg.size()){
  448.         return 0;
  449.     }else{
  450.         for(int i = self.deg.size() - 1; i > -1; --i){
  451.             if(self.deg[i] < other.deg[i]){
  452.                 return 1;
  453.             }else if(self.deg[i] > other.deg[i]){
  454.                 return 0;
  455.             }
  456.         }
  457.         return 0;
  458.     }
  459.  
  460. }
  461.  
  462. class Rational{
  463.     private:
  464.         BigInteger num;
  465.         BigInteger den;
  466.         void make_irred(BigInteger &self, BigInteger &other){
  467.             BigInteger gcd_ = gcd(self, other);
  468.             self /= gcd_;
  469.             other /= gcd_;
  470.         }
  471.         void Normalize(){
  472.             if(den.get_sign() == -1){
  473.                 num.change_sign();
  474.                 den.change_sign();
  475.             }
  476.             make_irred(num, den);
  477.         }
  478.     public:
  479.         Rational(const BigInteger &other){
  480.             num = BigInteger(other);
  481.             den = BigInteger(1);
  482.         }
  483.         Rational(const int other){
  484.             num = BigInteger(other);
  485.             den = BigInteger(1);
  486.         }
  487.         Rational(){
  488.             num = 0;
  489.             den = 1;
  490.         }
  491.         Rational& operator +=(const Rational &other){
  492.             num *= other.den;
  493.             num += other.num * den;
  494.             den *= other.den;
  495.            // make_irred(num, den);
  496.             Normalize();
  497.             return *this;
  498.         }
  499.  
  500.         Rational operator -() const {
  501.             Rational ans = *this;
  502.             ans.num *= -1;
  503.             return ans;
  504.         }
  505.         Rational& operator -=(const Rational &other){
  506.             *this += -other;
  507.             return *this;
  508.         }
  509.         Rational& operator *=(const Rational &other){
  510.             num *= other.num;
  511.             den *= other.den;
  512.            // make_irred(num, den);
  513.             Normalize();
  514.             return *this;
  515.         }
  516.         Rational& operator /=(const Rational &other){
  517.             num *= other.den;
  518.             den *= other.num;
  519.            // make_irred(num, den);
  520.             Normalize();
  521.             return *this;
  522.         }
  523.         Rational operator /(const Rational &other) const {
  524.             Rational ans = *this;
  525.             ans /= other;
  526.             return ans;
  527.         }
  528.         Rational& operator %=(const Rational &other){
  529.             *this = *this - *this / other * other;
  530.             return *this;
  531.         }
  532.         Rational operator %(const Rational &other) const {
  533.             Rational res = *this;
  534.             res %= other;
  535.             return res;
  536.         }
  537.         Rational operator *(const Rational &other) const {
  538.             Rational ans = *this;
  539.             ans *= other;
  540.             return ans;
  541.         }
  542.         Rational operator +(const Rational &other) const {
  543.             Rational ans = *this;
  544.             ans += other;
  545.             return ans;
  546.         }
  547.         Rational operator -(const Rational &other) const {
  548.             Rational ans = *this;
  549.             ans -= other;
  550.             return ans;
  551.         }
  552.         std::string toString() const {
  553.             std::string result = "";
  554.             if(num.get_sign() == -1){
  555.                 result += '-';
  556.             }
  557.             result += num.toString();
  558.             if(den != 1){
  559.                 result += '/';
  560.                 result += den.toString();
  561.             }
  562.             return result;
  563.         }
  564.         friend std::istream& operator>>(std::istream &in, Rational& self){
  565.             std::string input1;
  566.             std::string input2;
  567.             in >> input1 >> input2;
  568.             self.num = BigInteger(input1);
  569.             self.den = BigInteger(input2);
  570.             self.Normalize();
  571.             return in;
  572.         }
  573.         friend std::ostream& operator<<(std::ostream &out, const Rational& P){
  574.             //print(P.toString());
  575.             out << P.toString();
  576.             return out;
  577.         }
  578.         bool SmallerMod2(const Rational &self, const Rational &other) const {
  579.             Rational q = self / other;
  580.            // $$
  581.             if(SmallerMod(q.num, q.den)){
  582.                 return 1;
  583.             }
  584.             return 0;
  585.         }
  586.         bool operator ==(const Rational &other) const {
  587.             return toString() == other.toString();
  588.         }
  589.         bool operator <(const Rational &other) const {
  590.             bool smaller = SmallerMod2(*this, other);
  591.             if(num.get_sign() != other.num.get_sign()){
  592.                 if(num.get_sign() == 1){
  593.                     return 0;
  594.  
  595.                 }else{
  596.                     return 1;
  597.                 }
  598.             }
  599.             if(*this == other){
  600.                 return 0;
  601.             }
  602.             if(num.get_sign() == 1){
  603.                 return smaller;
  604.             }
  605.             return smaller ^ 1;
  606.         }
  607.         bool operator <=(const Rational &other) const {
  608.             return (*this < other) || (*this == other);
  609.         }
  610.         bool operator >(const Rational &other) const {
  611.             return other < *this;
  612.         }
  613.         bool operator >=(const Rational &other) const {
  614.             return (*this > other) || (*this == other);
  615.         }
  616.         bool operator !=(const Rational &other) const {
  617.             return !(*this == other);
  618.         }
  619.         Rational& operator =(const Rational &other){
  620.             num = other.num;
  621.             den = other.den;
  622.             return *this;
  623.         }
  624.  
  625. /*        bool operator ==(const int &other) const {
  626.             return *this == Rational(other);
  627.         }
  628.         bool operator <(const int &other) const {
  629.             return *this < Rational(other);
  630.         }
  631.         bool operator <=(const int &other) const {
  632.             return *this <= Rational(other);
  633.         }
  634.         bool operator >(const int &other) const {
  635.             return *this > Rational(other);
  636.         }
  637.         bool operator >=(const int &other) const {
  638.             return *this >= Rational(other);
  639.         }
  640.         bool operator !=(const int &other) const {
  641.             return *this != Rational(other);
  642.         }
  643.  
  644.          Rational& operator -=(const int other){
  645.             *this += -Rational(other);
  646.             return *this;
  647.         }
  648.         Rational& operator *=(const int other_){
  649.             Rational other = other_;
  650.             num *= other.num;
  651.             den *= other.den;
  652.            // make_irred(num, den);
  653.             Normalize();
  654.             return *this;
  655.         }
  656.         Rational& operator /=(const int other_){
  657.             Rational other = other_;
  658.             num *= other.den;
  659.             den *= other.num;
  660.            // make_irred(num, den);
  661.             Normalize();
  662.             return *this;
  663.         }
  664.         Rational operator /(const int other) const {
  665.             Rational ans = *this;
  666.             ans /= Rational(other);
  667.             return ans;
  668.         }
  669.         Rational& operator %=(const int other_){
  670.             Rational other = Rational(other_);
  671.             *this = *this - *this / other * other;
  672.             return *this;
  673.         }
  674.         Rational operator %(const int other) const {
  675.             Rational res = *this;
  676.             res %= Rational(other);
  677.             return res;
  678.         }
  679.         Rational operator *(const int other) const {
  680.             Rational ans = *this;
  681.             ans *= Rational(other);
  682.             return ans;
  683.         }
  684.         Rational operator +(const int other) const {
  685.             Rational ans = *this;
  686.             ans += Rational(other);
  687.             return ans;
  688.         }
  689.         Rational operator -(const int other) const {
  690.             Rational ans = *this;
  691.             ans -= Rational(other);
  692.             return ans;
  693.         }*/
  694.  
  695.         friend Rational operator +(const int self, const Rational& other){
  696.             return Rational(self) + other;
  697.         }
  698.         friend Rational operator -(const int self, const Rational& other){
  699.             return Rational(self) - other;
  700.         }
  701.         friend Rational operator *(const int self, const Rational& other){
  702.            return Rational(self) * other;
  703.         }
  704.         friend Rational operator /(const int self, const Rational& other){
  705.             return Rational(self) / other;
  706.         }
  707.         friend Rational operator %(const int self, const Rational& other){
  708.             return Rational(self) % other;
  709.         }
  710.         explicit operator bool() const {
  711.             return num;
  712.         }
  713.         std::string asDecimal(size_t precision) const {
  714.             BigInteger A = num % den;
  715.             std::string ans = (num / den).toString();
  716.             ans += '.';
  717.             std::string degree = "1";
  718.             for(size_t i = 0; i < precision; ++i){
  719.                 degree += '0';
  720.             }
  721.             std::cout << A << ' ' << den << ' ' << ans << '\n';
  722.             A *= BigInteger(degree);
  723.             ans += (A / den).toString();
  724.             return ans;
  725.         }
  726.         explicit operator double() const {
  727.             return std::stod(asDecimal(100));
  728.         }
  729. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement