Advertisement
zhangsongcui

Big Integer V2

May 1st, 2011
346
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.07 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <sstream>
  5. #include <iomanip>
  6. #include <cassert>
  7.  
  8. using namespace std;
  9.  
  10. class BigInt
  11. {
  12. private:
  13.     vector<unsigned> Data;      //ι€†εΊε­˜ζ”Ύ
  14.     //BigInt(vector<unsigned>&& data): Data(data) {}
  15.     //BigInt(vector<unsigned>::size_type size, unsigned val):Data(size, val) {}
  16.  
  17. public:
  18.     BigInt(): Data(1, 0) {};
  19.     BigInt(unsigned Num): Data(1, Num % 1000000000)
  20.     {
  21.         if (Num > 1000000000)
  22.             Data.push_back(Num / 1000000000);
  23.     }
  24.  
  25.     BigInt(const string& Num)
  26.     {
  27.         string::size_type len=Num.size();
  28.         Data.reserve(len / 9);
  29.         while (len>9)
  30.         {
  31.             len-=9;
  32.             Data.push_back(atol(Num.substr(len, 9).c_str()));
  33.         }
  34.         Data.push_back(atol((Num.substr(0, len)).c_str()));
  35.     }
  36. /*
  37.     BigInt& operator *=(unsigned rhs)
  38.     {
  39.         unsigned carry=0;
  40.         for (vector<unsigned>::iterator iter=Data.begin(); iter!=Data.end(); ++iter)
  41.         {
  42.             unsigned long long tmp=(unsigned long long)(*iter)*rhs+carry;
  43.             *iter=unsigned(tmp % 1000000000);
  44.             carry=unsigned(tmp / 1000000000);
  45.         }
  46.         if (carry)
  47.             Data.push_back(carry);
  48.         return *this;
  49.     }
  50.  
  51.     BigInt& operator /=(unsigned rhs)
  52.     {
  53.         unsigned long long carry=0;
  54.         for (vector<unsigned>::reverse_iterator rit=Data.rbegin(); rit!=Data.rend(); ++rit)
  55.         {
  56.             unsigned long long tmp=*rit+carry*1000000000;
  57.             *rit =unsigned(tmp / rhs);
  58.             carry=unsigned(tmp % rhs);
  59.         }
  60.         if (Data.back()==0)
  61.             Data.erase(Data.end()-1);
  62.         return *this;
  63.     }
  64. */
  65.     BigInt& operator +=(const BigInt& rhs)
  66.     {
  67.         bool carry=0;
  68.         if (Data.size() < rhs.Data.size())
  69.             Data.resize(rhs.Data.size());
  70.  
  71.         vector<unsigned>::iterator it1=Data.begin();
  72.         for (vector<unsigned>::const_iterator it2=rhs.Data.begin(); it2!=rhs.Data.end(); ++it1, ++it2)
  73.         {
  74.             unsigned tmp=*it1 + *it2 + carry;
  75.             *it1 =tmp % 1000000000;
  76.             carry=tmp > 999999999;
  77.         }
  78.         for (; carry && it1!=Data.end(); ++it1)
  79.         {
  80.             unsigned tmp=*it1 + carry;
  81.             *it1 =tmp % 1000000000;
  82.             carry=tmp > 999999999;
  83.         }
  84.         if (carry)
  85.             Data.push_back(1);
  86.         return *this;
  87.     }
  88. /*
  89.     BigInt& operator *=(const BigInt& rhs)
  90.     {
  91.         assert(this!=&rhs);
  92.         BigInt result;
  93.         for (vector<unsigned>::size_type i=0; i<rhs.Data.size(); ++i)
  94.         {
  95.             BigInt temp=*this;
  96.             temp*=rhs.Data[i];
  97.             temp.Data.insert(temp.Data.begin(), i, 0);
  98.             result+=temp;
  99.         }
  100.         return *this=move(result);
  101.     }
  102.  
  103.     string toString() const
  104.     {
  105.         ostringstream oss;
  106.         oss << *this;
  107.         return oss.str();
  108.     }
  109.  
  110.     bool operator ==(const BigInt& rhs) const
  111.     {
  112.         return Data==rhs.Data;
  113.     }
  114. */
  115.     friend ostream& operator <<(ostream& os, const BigInt& rhs)
  116.     {
  117.         vector<unsigned>::const_reverse_iterator riter=rhs.Data.rbegin();
  118.         os << *riter;
  119.         for (++riter; riter!=rhs.Data.rend(); ++riter)
  120.             os << setw(9) << setfill('0') << *riter;
  121.         return os;
  122.     }
  123.  
  124.     friend istream& operator >>(istream& is, BigInt& lhs)
  125.     {
  126.         string s;
  127.         cin >> s;
  128.         lhs=BigInt(s);
  129.         return is;
  130.     }
  131. };
  132.  
  133. int main()
  134. {
  135.     unsigned n;
  136.     BigInt a, b;
  137.     cin >> n;
  138.     for (unsigned i=1; i<=n; ++i)
  139.     {
  140.         cin >> a >> b;
  141.         cout << "Case " << i << ":\n" << a << " + " << b << " = ";
  142.         a+=b;
  143.         cout << a << '\n';
  144.     }
  145. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement