API tools faq
paste
Advertisement
KShah

Untitled

KShah
Nov 24th, 2021
1,068
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 15.32 KB | None | 0 0
raw download clone embed print report
  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
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!