Not a member of Pastebin yet?
                        Sign Up,
                        it unlocks many cool features!                    
                - #include <vector>
 - #include <string>
 - #include <iostream>
 - #include <algorithm>
 - class Big
 - {
 - using Hand = unsigned long;
 - static constexpr unsigned HandBits = sizeof(Hand)*8;
 - std::vector<Hand> hands;
 - public:
 - Big() : hands{} {}
 - Big(Hand val) : hands{val} {}
 - Big(std::string_view val) { for(char c: val) { *this *= 10; *this += Hand(c-'0'); } }
 - Big& operator>>=(unsigned n)
 - {
 - unsigned nwords = n/HandBits, c=nwords,d=c+1; n%=HandBits;
 - for(std::size_t a=0; a<hands.size(); ++a)
 - hands[a] = (((a+c) < hands.size() ? hands[a+c] : 0) >> n)
 - | (n ? (((a+d) < hands.size() ? hands[a+d] : 0) << (HandBits-n)) : 0);
 - return *this;
 - }
 - template<typename F1,typename F2>
 - Big& SubAdd(const Big& b, F1 op,F2 comp)
 - {
 - hands.resize(std::max(hands.size(), b.hands.size()));
 - Hand carry = 0, orig;
 - for(std::size_t a=0; a<hands.size(); ++a)
 - {
 - hands[a] = op(orig = hands[a], b.hands[a] + carry);
 - carry = comp(hands[a], orig) || (hands[a]==orig && b.hands[a] != 0);
 - }
 - if(carry) hands.push_back(1);
 - return *this;
 - }
 - Big& operator-=(const Big& b) { return SubAdd(b, std::minus{}, std::greater{}); }
 - Big& operator+=(const Big& b) { return SubAdd(b, std::plus{}, std::less{}); }
 - bool operator<(const Big& b) const
 - {
 - return (Big(*this) -= b).hands.size() > std::max(hands.size(), b.hands.size());
 - //for(std::size_t n=std::max(hands.size(), b.hands.size()); n-- > 0; )
 - // if(Hand x = (n<hands.size()?hands[n]:0), y = (n<b.hands.size()?b.hands[n]:0);
 - // x != y) return x < y;
 - //return false;
 - }
 - Big& operator*=(const Big& b)
 - {
 - for(Big a=std::move(*this), c=b; Big{} < a; a>>=1, c+=c) { if(a.hands[0]&1) *this += c; }
 - return *this;
 - }
 - static Big DivMod(Big& result, Big&& divisor)
 - {
 - for(Big remain = std::move(result), multiple=1; ; divisor+=divisor,multiple+=multiple)
 - if(!(divisor < remain))
 - {
 - do if(!(remain < divisor)) { remain -= divisor; result += multiple; }
 - while(divisor>>=1, Big{} < (multiple>>=1));
 - return remain;
 - }
 - }
 - std::string to_string() const
 - {
 - std::string str;
 - Big value = *this, remain;
 - while(Big{} < value) { str.insert(0, 1, '0' + (remain = DivMod(value, 10)).hands[0]); }
 - if(str.empty()) str += '0';
 - return str;
 - }
 - };
 - int main(int argc, char** argv)
 - {
 - Big a(argv[1]), b(argv[2]);
 - a *= b;
 - std::cout << a.to_string() << '\n';
 - }
 
Advertisement
 
                    Add Comment                
                
                        Please, Sign In to add comment