Advertisement
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
Advertisement