fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. class BigInt{
  7.     string digits;
  8. public:
  9.  
  10.     //Constructors:
  11.     BigInt(unsigned long long n = 0);
  12.     BigInt(string &);
  13.     BigInt(const char *);
  14.     BigInt(BigInt &);
  15.  
  16.     //Helper Functions:
  17.     friend void divide_by_2(BigInt &a);
  18.     friend bool Null(const BigInt &);
  19.     friend int Length(const BigInt &);
  20.     int operator[](const int)const;
  21.  
  22.                /* * * * Operator Overloading * * * */
  23.  
  24.     //Direct assignment
  25.     BigInt &operator=(const BigInt &);
  26.  
  27.     //Post/Pre - Incrementation
  28.     BigInt &operator++();
  29.     BigInt operator++(int temp);
  30.     BigInt &operator--();
  31.     BigInt operator--(int temp);
  32.  
  33.     //Addition and Subtraction
  34.     friend BigInt &operator+=(BigInt &, const BigInt &);
  35.     friend BigInt operator+(const BigInt &, const BigInt &);
  36.     friend BigInt operator-(const BigInt &, const BigInt &);
  37.     friend BigInt &operator-=(BigInt &, const BigInt &);
  38.  
  39.     //Comparison operators
  40.     friend bool operator==(const BigInt &, const BigInt &);
  41.     friend bool operator!=(const BigInt &, const BigInt &);
  42.  
  43.     friend bool operator>(const BigInt &, const BigInt &);
  44.     friend bool operator>=(const BigInt &, const BigInt &);
  45.     friend bool operator<(const BigInt &, const BigInt &);
  46.     friend bool operator<=(const BigInt &, const BigInt &);
  47.  
  48.     //Multiplication and Division
  49.     friend BigInt &operator*=(BigInt &, const BigInt &);
  50.     friend BigInt operator*(const BigInt &, const BigInt &);
  51.     friend BigInt &operator/=(BigInt &, const BigInt &);
  52.     friend BigInt operator/(const BigInt &, const BigInt &);
  53.  
  54.     //Modulo
  55.     friend BigInt operator%(const BigInt &, const BigInt &);
  56.     friend BigInt &operator%=(BigInt &, const BigInt &);
  57.  
  58.     //Power Function
  59.     friend BigInt &operator^=(BigInt &,const BigInt &);
  60.     friend BigInt operator^(BigInt &, const BigInt &);
  61.  
  62.     //Square Root Function
  63.     friend BigInt sqrt(BigInt &a);
  64.  
  65.     //Read and Write
  66.     friend ostream &operator<<(ostream &,const BigInt &);
  67.     friend istream &operator>>(istream &, BigInt &);
  68.  
  69.     //Others
  70.     friend BigInt NthCatalan(int n);
  71.     friend BigInt NthFibonacci(int n);
  72.     friend BigInt Factorial(int n);
  73. };
  74.  
  75. BigInt::BigInt(string & s){
  76.     digits = "";
  77.     int n = s.size();
  78.     for (int i = n - 1; i >= 0;i--){
  79.         if(!isdigit(s[i]))
  80.             throw("ERROR");
  81.         digits.push_back(s[i] - '0');
  82.     }
  83. }
  84. BigInt::BigInt(unsigned long long nr){
  85.     do{
  86.         digits.push_back(nr % 10);
  87.         nr /= 10;
  88.     } while (nr);
  89. }
  90. BigInt::BigInt(const char *s){
  91.     digits = "";
  92.     for (int i = strlen(s) - 1; i >= 0;i--)
  93.     {
  94.         if(!isdigit(s[i]))
  95.             throw("ERROR");
  96.         digits.push_back(s[i] - '0');
  97.     }
  98. }
  99. BigInt::BigInt(BigInt & a){
  100.     digits = a.digits;
  101. }
  102.  
  103. bool Null(const BigInt& a){
  104.     if(a.digits.size() == 1 && a.digits[0] == 0)
  105.         return true;
  106.     return false;
  107. }
  108. int Length(const BigInt & a){
  109.     return a.digits.size();
  110. }
  111. int BigInt::operator[](const int index)const{
  112.     if(digits.size() <= index | index < 0)
  113.         throw("ERROR");
  114.     return digits[index];
  115. }
  116. bool operator==(const BigInt &a, const BigInt &b){
  117.     return a.digits == b.digits;
  118. }
  119. bool operator!=(const BigInt & a,const BigInt &b){
  120.     return !(a == b);
  121. }
  122. bool operator<(const BigInt&a,const BigInt&b){
  123.     int n = Length(a), m = Length(b);
  124.     if(n != m)
  125.         return n < m;
  126.     while(n--)
  127.         if(a.digits[n] != b.digits[n])
  128.             return a.digits[n] < b.digits[n];
  129.     return false;
  130. }
  131. bool operator>(const BigInt&a,const BigInt&b){
  132.     return b < a;
  133. }
  134. bool operator>=(const BigInt&a,const BigInt&b){
  135.     return !(a < b);
  136. }
  137. bool operator<=(const BigInt&a,const BigInt&b){
  138.     return !(a > b);
  139. }
  140.  
  141. BigInt &BigInt::operator=(const BigInt &a){
  142.     digits = a.digits;
  143.     return *this;
  144. }
  145.  
  146. BigInt &BigInt::operator++(){
  147.     int i, n = digits.size();
  148.     for (i = 0; i < n && digits[i] == 9;i++)
  149.         digits[i] = 0;
  150.     if(i == n)
  151.         digits.push_back(1);
  152.     else
  153.         digits[i]++;
  154.     return *this;
  155. }
  156. BigInt BigInt::operator++(int temp){
  157.     BigInt aux;
  158.     aux = *this;
  159.     ++(*this);
  160.     return aux;
  161. }
  162.  
  163. BigInt &BigInt::operator--(){
  164.     if(digits[0] == 0 && digits.size() == 1)
  165.         throw("UNDERFLOW");
  166.     int i, n = digits.size();
  167.     for (i = 0; digits[i] == 0 && i < n;i++)
  168.         digits[i] = 9;
  169.     digits[i]--;
  170.     if(n > 1 && digits[n - 1] == 0)
  171.         digits.pop_back();
  172.     return *this;
  173. }
  174. BigInt BigInt::operator--(int temp){
  175.     BigInt aux;
  176.     aux = *this;
  177.     --(*this);
  178.     return aux;
  179. }
  180.  
  181. BigInt &operator+=(BigInt &a,const BigInt& b){
  182.     int t = 0, s, i;
  183.     int n = Length(a), m = Length(b);
  184.     if(m > n)
  185.         a.digits.append(m - n, 0);
  186.     n = Length(a);
  187.     for (i = 0; i < n;i++){
  188.         if(i < m)
  189.             s = (a.digits[i] + b.digits[i]) + t;
  190.         else
  191.             s = a.digits[i] + t;
  192.         t = s / 10;
  193.         a.digits[i] = (s % 10);
  194.     }
  195.     if(t)
  196.         a.digits.push_back(t);
  197.     return a;
  198. }
  199. BigInt operator+(const BigInt &a, const BigInt &b){
  200.     BigInt temp;
  201.     temp = a;
  202.     temp += b;
  203.     return temp;
  204. }
  205.  
  206. BigInt &operator-=(BigInt&a,const BigInt &b){
  207.     if(a < b)
  208.         throw("UNDERFLOW");
  209.     int n = Length(a), m = Length(b);
  210.     int i, t = 0, s;
  211.     for (i = 0; i < n;i++){
  212.         if(i < m)
  213.             s = a.digits[i] - b.digits[i]+ t;
  214.         else
  215.             s = a.digits[i]+ t;
  216.         if(s < 0)
  217.             s += 10,
  218.             t = -1;
  219.         else
  220.             t = 0;
  221.         a.digits[i] = s;
  222.     }
  223.     while(n > 1 && a.digits[n - 1] == 0)
  224.         a.digits.pop_back(),
  225.         n--;
  226.     return a;
  227. }
  228. BigInt operator-(const BigInt& a,const BigInt&b){
  229.     BigInt temp;
  230.     temp = a;
  231.     temp -= b;
  232.     return temp;
  233. }
  234.  
  235. BigInt &operator*=(BigInt &a, const BigInt &b)
  236. {
  237.     if(Null(a) || Null(b)){
  238.         a = BigInt();
  239.         return a;
  240.     }
  241.     int n = a.digits.size(), m = b.digits.size();
  242.     vector<int> v(n + m, 0);
  243.     for (int i = 0; i < n;i++)
  244.         for (int j = 0; j < m;j++){
  245.             v[i + j] += (a.digits[i] ) * (b.digits[j]);
  246.         }
  247.     n += m;
  248.     a.digits.resize(v.size());
  249.     for (int s, i = 0, t = 0; i < n; i++)
  250.     {
  251.         s = t + v[i];
  252.         v[i] = s % 10;
  253.         t = s / 10;
  254.         a.digits[i] = v[i] ;
  255.     }
  256.     for (int i = n - 1; i >= 1 && !v[i];i--)
  257.             a.digits.pop_back();
  258.     return a;
  259. }
  260. BigInt operator*(const BigInt&a,const BigInt&b){
  261.     BigInt temp;
  262.     temp = a;
  263.     temp *= b;
  264.     return temp;
  265. }
  266.  
  267. BigInt &operator/=(BigInt& a,const BigInt &b){
  268.     if(Null(b))
  269.         throw("Arithmetic Error: Division By 0");
  270.     if(a < b){
  271.         a = BigInt();
  272.         return a;
  273.     }
  274.     if(a == b){
  275.         a = BigInt(1);
  276.         return a;
  277.     }
  278.     int i, lgcat = 0, cc;
  279.     int n = Length(a), m = Length(b);
  280.     vector<int> cat(n, 0);
  281.     BigInt t;
  282.     for (i = n - 1; t * 10 + a.digits[i]  < b;i--){
  283.         t *= 10;
  284.         t += a.digits[i] ;
  285.     }
  286.     for (; i >= 0; i--){
  287.         t = t * 10 + a.digits[i];
  288.         for (cc = 9; cc * b > t;cc--);
  289.         t -= cc * b;
  290.         cat[lgcat++] = cc;
  291.     }
  292.     a.digits.resize(cat.size());
  293.     for (i = 0; i < lgcat;i++)
  294.         a.digits[i] = cat[lgcat - i - 1];
  295.     a.digits.resize(lgcat);
  296.     return a;
  297. }
  298. BigInt operator/(const BigInt &a,const BigInt &b){
  299.     BigInt temp;
  300.     temp = a;
  301.     temp /= b;
  302.     return temp;
  303. }
  304.  
  305. BigInt &operator%=(BigInt& a,const BigInt &b){
  306.     if(Null(b))
  307.         throw("Arithmetic Error: Division By 0");
  308.     if(a < b){
  309.         return a;
  310.     }
  311.     if(a == b){
  312.         a = BigInt();
  313.         return a;
  314.     }
  315.     int i, lgcat = 0, cc;
  316.     int n = Length(a), m = Length(b);
  317.     vector<int> cat(n, 0);
  318.     BigInt t;
  319.     for (i = n - 1; t * 10 + a.digits[i] < b;i--){
  320.         t *= 10;
  321.         t += a.digits[i];
  322.     }
  323.     for (; i >= 0; i--){
  324.         t = t * 10 + a.digits[i];
  325.         for (cc = 9; cc * b > t;cc--);
  326.         t -= cc * b;
  327.         cat[lgcat++] = cc;
  328.     }
  329.     a = t;
  330.     return a;
  331. }
  332. BigInt operator%(const BigInt &a,const BigInt &b){
  333.     BigInt temp;
  334.     temp = a;
  335.     temp %= b;
  336.     return temp;
  337. }
  338.  
  339. BigInt &operator^=(BigInt & a,const BigInt & b){
  340.     BigInt Exponent, Base(a);
  341.     Exponent = b;
  342.     a = 1;
  343.     while(!Null(Exponent)){
  344.         if(Exponent[0] & 1)
  345.             a *= Base;
  346.         Base *= Base;
  347.         divide_by_2(Exponent);
  348.     }
  349.     return a;
  350. }
  351. BigInt operator^(BigInt & a,BigInt & b){
  352.     BigInt temp(a);
  353.     temp ^= b;
  354.     return temp;
  355. }
  356.  
  357. void divide_by_2(BigInt & a){
  358.     int add = 0;
  359.     for (int i = a.digits.size() - 1; i >= 0;i--){
  360.         int digit = (a.digits[i] >> 1) + add;
  361.         add = ((a.digits[i] & 1) * 5);
  362.         a.digits[i] = digit;
  363.     }
  364.     while(a.digits.size() > 1 && !a.digits.back())
  365.         a.digits.pop_back();
  366. }
  367.  
  368. BigInt sqrt(BigInt & a){
  369.     BigInt left(1), right(a), v(1), mid, prod;
  370.     divide_by_2(right);
  371.     while(left <= right){
  372.         mid += left;
  373.         mid += right;
  374.         divide_by_2(mid);
  375.         prod = (mid * mid);
  376.         if(prod <= a){
  377.             v = mid;
  378.             ++mid;
  379.             left = mid;
  380.         }
  381.         else{
  382.             --mid;
  383.             right = mid;
  384.         }
  385.         mid = BigInt();
  386.     }
  387.     return v;
  388. }
  389.  
  390. BigInt NthCatalan(int n){
  391.     BigInt a(1),b;
  392.     for (int i = 2; i <= n;i++)
  393.         a *= i;
  394.     b = a;
  395.     for (int i = n + 1; i <= 2 * n;i++)
  396.         b *= i;
  397.     a *= a;
  398.     a *= (n + 1);
  399.     b /= a;
  400.     return b;
  401. }
  402.  
  403. BigInt NthFibonacci(int n){
  404.     BigInt a(1), b(1), c;
  405.     if(!n)
  406.         return c;
  407.     n--;
  408.     while(n--){
  409.         c = a + b;
  410.         b = a;
  411.         a = c;
  412.     }
  413.     return b;
  414. }
  415.  
  416. BigInt Factorial(int n){
  417.     BigInt f(1);
  418.     for (int i = 2; i <= n;i++)
  419.         f *= i;
  420.     return f;
  421. }
  422.  
  423. istream &operator>>(istream &in,BigInt&a){
  424.     string s;
  425.     in >> s;
  426.     int n = s.size();
  427.     for (int i = n - 1; i >= 0;i--){
  428.         if(!isdigit(s[i]))
  429.             throw("INVALID NUMBER");
  430.         a.digits[n - i - 1] = s[i];
  431.     }
  432.     return in;
  433. }
  434.  
  435. ostream &operator<<(ostream &out,const BigInt &a){
  436.     for (int i = a.digits.size() - 1; i >= 0;i--)
  437.         cout << (short)a.digits[i];
  438.     return cout;
  439. }
  440.  
  441.  
  442. int main(){
  443.     ios_base::sync_with_stdio(false);
  444.     cin.tie(nullptr);
  445.     cout.tie(nullptr);
  446.     string sa, sb;
  447.     cin >> sa >> sb;
  448.     BigInt a(sa), b(sb);
  449.     cout << a * b;
  450. }
  451.  
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UYv2yH
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!