Advertisement
KShah

Untitled

Nov 24th, 2021
770
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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.        
  317.         friend BigInteger operator +(const int self, const BigInteger& other){
  318.             return BigInteger(self) + other;
  319.         }
  320.         friend BigInteger operator-(const int self, const BigInteger& other){
  321.             return BigInteger(self) - other;
  322.         }
  323.         friend BigInteger operator*(const int self, const BigInteger& other){
  324.            return BigInteger(self) * other;
  325.         }
  326.         friend BigInteger operator/(const int self, const BigInteger& other){
  327.             return BigInteger(self) / other;
  328.         }
  329.         friend BigInteger operator%(const int self, const BigInteger& other){
  330.             return BigInteger(self) % other;
  331.         }
  332.         operator bool() const {
  333.             return deg[0] || deg.size() > 1;
  334.         }
  335.         BigInteger operator *(const BigInteger &other) const {
  336.             BigInteger composition;
  337.             composition.deg.resize(deg.size() + other.deg.size());
  338.             for(size_t i = 0; i < deg.size(); ++i){
  339.                 for(size_t j = 0; j < other.deg.size(); ++j){
  340.                     composition.deg[i + j] += deg[i] * other.deg[j];
  341.                 }
  342.             }
  343.             composition.sign = sign * other.sign;
  344.             composition.Normalize();
  345.             return composition;
  346.         }
  347.         BigInteger& operator *=(const BigInteger &other){
  348.             *this = *this * other;
  349.             return *this;
  350.         }
  351.         /*BigInteger operator /(const BigInteger &other) const {
  352.             BigInteger A = *this, B = other;
  353.             A.sign = 1;
  354.             B.sign = 1;
  355.             BigInteger ans = 0;
  356.             ans.sign = sign * other.sign;
  357.             while(A.deg.size() >= B.deg.size()){
  358.                // std::cout << "   " << A.deg.back() << ' ' << B.deg.back() << std::endl;
  359.                 BigInteger P = BigInteger((A.deg.back() + B.deg.back() - 1 + 1) / B.deg.back(), A.deg.size() - B.deg.size() + 1);
  360.                 ans += P;
  361.                 A -= P * B;
  362.             }
  363.             return ans;
  364.         }*/
  365.         BigInteger operator /(const BigInteger &other) const {
  366.             BigInteger result = *this;
  367.             result /= other;
  368.             return result;
  369.         }
  370.         BigInteger& operator %=(const BigInteger &other){
  371.             *this -= *this / other * other;
  372.             return *this;
  373.         }
  374.         BigInteger operator %(const BigInteger &other) const {
  375.             return *this - other * (*this / other);
  376.         }
  377.         BigInteger& operator /=(const BigInteger &other){
  378.          //   print(deg)
  379.            // print(other.deg)
  380.             if (SmallerMod(*this, other)){
  381.                 *this = 0;
  382.                 return *this;
  383.             }
  384.             sign *= other.sign;
  385.             reverse();
  386.             std::vector<int> new_deg;
  387.             BigInteger val = 0;
  388.             //$$
  389.             for(size_t i = 0; i < deg.size() + 1; ++i) {
  390.                 //print(new_deg)
  391.                 //std::cout << val << '\n';
  392.                 new_deg.push_back(divide_two(val, other));
  393.                 //std::cout << "  " << val << ' ' << new_deg.back() << '\n';
  394.                 val -= other * new_deg.back();
  395.                 if(i == deg.size()){
  396.                     break;
  397.                 }
  398.                 val *= 10;
  399.                 val += deg[i];
  400.             }
  401.             deg = new_deg;
  402.             reverse();
  403.             Normalize();
  404.             return *this;
  405.         }
  406.         int divide_two(const BigInteger &self, const BigInteger &other) {
  407.             for(int i = 0; i < 10; ++i){
  408.                 if (other * (i + 1) > self || -other * (i + 1) > self) {
  409.                     return i;
  410.                 }
  411.             }
  412.             return 0;
  413.         }
  414.         BigInteger operator /(const int other) const {
  415.             return *this / BigInteger(other);
  416.         }
  417.         BigInteger& operator %=(const int other){
  418.             *this %= BigInteger(other);
  419.             return *this;
  420.         }
  421.         BigInteger operator %(const int other) const {
  422.             return *this % BigInteger(other);
  423.         }
  424.         BigInteger& operator /=(const int other){
  425.             *this /= BigInteger(other);
  426.             return *this;
  427.         }
  428.         void change_sign(){
  429.             sign *= -1;
  430.         }
  431.         int get_sign() const {
  432.             return sign;
  433.         }
  434.         friend bool SmallerMod(const BigInteger&, const BigInteger&);
  435. };
  436.  
  437. template<typename T>
  438. T gcd(T a, T b){
  439.     while(b){
  440.         a = a % b;
  441.         std::swap(a, b);
  442.     }
  443.     return a;
  444. }
  445. bool SmallerMod(const BigInteger &self, const BigInteger &other){
  446.     if(self.deg.size() < other.deg.size()){
  447.         return 1;
  448.     }else if(self.deg.size() > other.deg.size()){
  449.         return 0;
  450.     }else{
  451.         for(int i = self.deg.size() - 1; i > -1; --i){
  452.             if(self.deg[i] < other.deg[i]){
  453.                 return 1;
  454.             }else if(self.deg[i] > other.deg[i]){
  455.                 return 0;
  456.             }
  457.         }
  458.         return 0;
  459.     }
  460.  
  461. }
  462.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement