21 条题解
-
0
#include<bits/stdc++.h> #define yuasfy7189dyjkwqafyi7ahakjsfgb872314fg7b8qgcrg4cagujbyrf67b4gs using #define tqgyfduasyufasfg3814aw678f432yasd6f7g32yaw687f34fae6fuaafdsag86yg5234fg9gy namespace #define ydwuiygtqffafyut34gf78bgasg67f8afgf4367ffasd1tygf9q67f342avs6f7ys6adfyvuyayhufd std yuasfy7189dyjkwqafyi7ahakjsfgb872314fg7b8qgcrg4cagujbyrf67b4gs tqgyfduasyufasfg3814aw678f432yasd6f7g32yaw687f34fae6fuaafdsag86yg5234fg9gy ydwuiygtqffafyut34gf78bgasg67f8afgf4367ffasd1tygf9q67f342avs6f7ys6adfyvuyayhufd; #define ttttyuasfgqewrgvbdfchjafashgfjq3uy long #define fgtdhsajfgejykfgyagsdgyfkafgrewgfasdtasasdjksdaf 0 #define uyftgdasjkhfgadsyufsdahjfgasdfjasdfgdsa return #define eqtryuiwqfgghashjfgcasdfcasfdsafgjherwbvuyfa long #define qweyuasdfhdsabjfghafdsgfvuqewrgftvfuayjdsfasdjyttfgvdsaghsda main #define rtqyuwefgdsjhavfasgjvfgrweqfybvdastfvbyutqwerkyufttyu <% #define tftasdjferwgqjtyufkgyudgvafadsyjfsdaykjfgasdyfgvsdjjfh %> ttttyuasfgqewrgvbdfchjafashgfjq3uy eqtryuiwqfgghashjfgcasdfcasfdsafgjherwbvuyfa fagydfdeykajfviureqgfhdasvtyujdasfgdsatyfgjhtfgajsdfdasdffasdgrgsfdfads; eqtryuiwqfgghashjfgcasdfcasfdsafgjherwbvuyfa ttttyuasfgqewrgvbdfchjafashgfjq3uy hgfyuafujerwbgvfkdgasfjhasdtyweqrfygdtsajfgsdajyhuftgdsajtyudasfsadthftgsadhfjdasgfjasdgfhjghjsahdfghasdf; #define gfydufkafyergwfjhdasfsdakjufytgdsafgutdsamfygsdatytugfhfvadsdsa scanf #define fygiuasdkjfywerqyfiqwegfvyhsafvaskhjfgdshkjfgsdafygkdsagftgdsayjf printf int qweyuasdfhdsabjfghafdsgfvuqewrgftvfuayjdsfasdjyttfgvdsaghsda() rtqyuwefgdsjhavfasgjvfgrweqfybvdastfvbyutqwerkyufttyu gfydufkafyergwfjhdasfsdakjufytgdsafgutdsamfygsdatytugfhfvadsdsa("%lld%lld",&fagydfdeykajfviureqgfhdasvtyujdasfgdsatyfgjhtfgajsdfdasdffasdgrgsfdfads,&hgfyuafujerwbgvfkdgasfjhasdtyweqrfygdtsajfgsdajyhuftgdsajtyudasfsadthftgsadhfjdasgfjasdgfhjghjsahdfghasdf); fygiuasdkjfywerqyfiqwegfvyhsafvaskhjfgdshkjfgsdafygkdsagftgdsayjf("%lld",fagydfdeykajfviureqgfhdasvtyujdasfgdsatyfgjhtfgajsdfdasdffasdgrgsfdfads+hgfyuafujerwbgvfkdgasfjhasdtyweqrfygdtsajfgsdajyhuftgdsajtyudasfsadthftgsadhfjdasgfjasdgfhjghjsahdfghasdf); uyftgdasjkhfgadsyufsdahjfgasdfjasdfgdsa fgtdhsajfgejykfgyagsdgyfkafgrewgfasdtasasdjksdaf; tftasdjferwgqjtyufkgyudgvafadsyjfsdaykjfgasdyfgvsdjjfh
写成这样了,居然还能跑。
-
-2
如果不使用高精度,TA会伤心的555~
#ifndef BIGINT_H_ #define BIGINT_H_ #include <iostream> #include <string> #include <vector> using namespace std; class UnsignedBigInt { public: typedef unsigned int value_type; typedef vector<value_type>::size_type size_type; typedef unsigned long long maxinteger_type; private: vector<value_type> val; //鍊硷紝姣忎綅涓€涓暟瀛楋紝閲囩敤椤哄簭瀛樺偍 private: public: //鏋勯€犲嚱鏁?瑙f瀽鍑芥暟 UnsignedBigInt(); UnsignedBigInt(string& s); UnsignedBigInt(string&& s); UnsignedBigInt(const maxinteger_type _val); UnsignedBigInt(const vector<value_type>& val); UnsignedBigInt(const vector<value_type>&& val); ~UnsignedBigInt() = default; //绫诲瀷杞崲鍑芥暟 inline explicit operator bool() const { return !val.empty(); } explicit operator string() const; //鏅€氬嚱鏁? const UnsignedBigInt factorial() const; //杩斿洖鑷繁鐨勯樁涔? const maxinteger_type value() const; //杞崲鎴愭暣鍨嬶紝鐢ㄦ櫘閫氬嚱鏁伴伩鍏嶄换浣曟剰澶栵紝娉ㄦ剰鏁板お澶т細瓒婄晫 //閲嶈浇绠楁湳杩愮畻绗? const UnsignedBigInt operator+(const UnsignedBigInt&) const; const UnsignedBigInt operator+(const UnsignedBigInt&&) const; const UnsignedBigInt operator-(const UnsignedBigInt&) const; const UnsignedBigInt operator-(const UnsignedBigInt&&) const; const UnsignedBigInt operator*(const UnsignedBigInt&) const; const UnsignedBigInt operator*(const UnsignedBigInt&&) const; const UnsignedBigInt operator/(const UnsignedBigInt&) const; const UnsignedBigInt operator/(const UnsignedBigInt&&) const; const UnsignedBigInt operator%(const UnsignedBigInt&) const; const UnsignedBigInt operator%(const UnsignedBigInt&&) const; const UnsignedBigInt operator^(const maxinteger_type&) const; //蹇€熷箓锛岄€夌敤ull鏄洜涓哄埌杩欓噷vector鐨剆ize宸茬粡鍒版瀬闄愪簡銆? const UnsignedBigInt operator^(const maxinteger_type&&) const; //蹇€熷箓锛岄€夌敤ull鏄洜涓哄埌杩欓噷vector鐨剆ize宸茬粡鍒版瀬闄愪簡銆? inline const UnsignedBigInt operator+=(const UnsignedBigInt& a) { return ((*this) = (*this) + a); } inline const UnsignedBigInt operator+=(const UnsignedBigInt&& a) { return ((*this) = (*this) + a); } inline const UnsignedBigInt operator-=(const UnsignedBigInt& a) { return ((*this) = (*this) - a); } inline const UnsignedBigInt operator-=(const UnsignedBigInt&& a) { return ((*this) = (*this) - a); } inline const UnsignedBigInt operator*=(const UnsignedBigInt& a) { return ((*this) = (*this) * a); } inline const UnsignedBigInt operator*=(const UnsignedBigInt&& a) { return ((*this) = (*this) * a); } inline const UnsignedBigInt operator/=(const UnsignedBigInt& a) { return ((*this) = (*this) / a); } inline const UnsignedBigInt operator/=(const UnsignedBigInt&& a) { return ((*this) = (*this) / a); } inline const UnsignedBigInt operator%=(const maxinteger_type& a) { return ((*this) = (*this) % a); } inline const UnsignedBigInt operator%=(const maxinteger_type&& a) { return ((*this) = (*this) % a); } inline const UnsignedBigInt operator^=(const maxinteger_type& a) { return ((*this) = (*this) ^ a); } inline const UnsignedBigInt operator^=(const maxinteger_type&& a) { return ((*this) = (*this) ^ a); } inline const UnsignedBigInt operator++() { return ((*this) += 1U); } inline const UnsignedBigInt operator++(int) { auto res = (*this); ++(*this); return res; } //閲嶈浇姣旇緝杩愮畻绗? bool operator<(const UnsignedBigInt&) const; bool operator<=(const UnsignedBigInt&) const; inline bool operator>(const UnsignedBigInt& a) const { return !((*this) <= a); } inline bool operator>=(const UnsignedBigInt& a) const { return !((*this) < a); } bool operator==(const UnsignedBigInt&) const; inline bool operator!=(const UnsignedBigInt& a) const { return !((*this) == a); } }; inline ostream& operator<<(ostream& os, const UnsignedBigInt& a) { os << string(a); return os; } inline ostream& operator<<(ostream& os, const UnsignedBigInt&& a) { os << string(a); return os; } istream& operator>>(istream& is, UnsignedBigInt& a); istream& operator>>(istream& is, UnsignedBigInt&& a); class BigInt { public: typedef UnsignedBigInt::value_type value_type; typedef UnsignedBigInt::size_type size_type; typedef make_signed<UnsignedBigInt::maxinteger_type>::type maxinteger_type; private: UnsignedBigInt val; //鍊硷紝姣忎綅涓€涓暟瀛楋紝閲囩敤椤哄簭瀛樺偍 bool sign; //绗﹀彿锛?姝f暟1璐熸暟 public: //鏋勯€犲嚱鏁?瑙f瀽鍑芥暟 BigInt(); BigInt(string& s); BigInt(string&& s); BigInt(maxinteger_type _val); BigInt(const UnsignedBigInt&); BigInt(UnsignedBigInt&&); ~BigInt() {} //绫诲瀷杞崲鍑芥暟 inline explicit operator bool() const { return bool(val); } explicit operator string() const; explicit operator UnsignedBigInt() const; //鏅€氬嚱鏁? bool isnegative() const; //杩斿洖鏄惁涓鸿礋鏁? const BigInt factorial() const; //杩斿洖鑷繁鐨勯樁涔? //閲嶈浇绠楁湳杩愮畻绗? const BigInt operator-() const; const BigInt operator+(const BigInt&) const; const BigInt operator+(const BigInt&&) const; const BigInt operator-(const BigInt&) const; const BigInt operator-(const BigInt&&) const; const BigInt operator*(const BigInt&) const; const BigInt operator*(const BigInt&&) const; const BigInt operator/(const BigInt&) const; const BigInt operator/(const BigInt&&) const; const BigInt operator%(const BigInt&) const; const BigInt operator%(const BigInt&&) const; const BigInt operator^(const maxinteger_type&) const; const BigInt operator^(const maxinteger_type&&) const; inline const BigInt operator+=(const BigInt& a) { return ((*this) = (*this) + a); } inline const BigInt operator+=(const BigInt&& a) { return ((*this) = (*this) + a); } inline const BigInt operator-=(const BigInt& a) { return ((*this) = (*this) - a); } inline const BigInt operator-=(const BigInt&& a) { return ((*this) = (*this) - a); } inline const BigInt operator*=(const BigInt& a) { return ((*this) = (*this) * a); } inline const BigInt operator*=(const BigInt&& a) { return ((*this) = (*this) * a); } inline const BigInt operator/=(const BigInt& a) { return ((*this) = (*this) / a); } inline const BigInt operator/=(const BigInt&& a) { return ((*this) = (*this) / a); } inline const BigInt operator^=(const maxinteger_type& a) { return ((*this) = (*this) ^ a); } inline const BigInt operator^=(const maxinteger_type&& a) { return ((*this) = (*this) ^ a); } inline const BigInt operator++() { return ((*this) += 1U); } inline const BigInt operator++(int) { auto res = (*this); ++(*this); return res; } //閲嶈浇姣旇緝杩愮畻绗? bool operator<(const BigInt&) const; bool operator<(const BigInt&&) const; bool operator<=(const BigInt&) const; bool operator<=(const BigInt&&) const; bool operator==(const BigInt&) const; bool operator==(const BigInt&&) const; inline bool operator>(const BigInt& a) const { return !((*this) <= a); } inline bool operator>(const BigInt&& a) const { return !((*this) <= a); } inline bool operator>=(const BigInt& a) const { return !((*this) < a); } inline bool operator>=(const BigInt&& a) const { return !((*this) < a); } inline bool operator!=(const BigInt& a) const { return !((*this) == a); } inline bool operator!=(const BigInt&& a) const { return !((*this) == a); } }; inline ostream& operator<<(ostream& os, const BigInt& a) { os << string(a); return os; } inline ostream& operator<<(ostream& os, const BigInt&& a) { os << string(a); return os; } istream& operator>>(istream& is, BigInt& a); istream& operator>>(istream& is, BigInt&& a); #endif #ifndef BIGINT_CPP_CPP_ #define BIGINT_CPP_CPP_ #include <algorithm> #include <cmath> #include <exception> #include <type_traits> #include <vector> //鏋勯€犲嚱鏁?瑙f瀽鍑芥暟 UnsignedBigInt::UnsignedBigInt() { val.push_back(0); } UnsignedBigInt::UnsignedBigInt(string& s) { string::size_type len = s.length(), i = 0; while (i < len && s[i] == '0') ++i; if (i == len) { val.push_back(0); return; } for (; i < len; i++) { if (isdigit(s[i])) val.push_back(s[i] - '0'); else { val = vector<value_type>(); cerr << "UnsignedBigInt::UnsignedBigInt(string& s):find a char " "not number!\n"; throw exception(); return; } } } UnsignedBigInt::UnsignedBigInt(string&& s) { string::size_type len = s.length(), i = 0; while (i < len && s[i] == '0') ++i; if (i == len - 1) { val.push_back(0); return; } for (; i < len; i++) { if (isdigit(s[i])) val.push_back(s[i] - '0'); else { val = vector<value_type>(); cerr << "UnsignedBigInt::UnsignedBigInt(string&& s):find a char " "not number!\n"; throw exception(); return; } } } UnsignedBigInt::UnsignedBigInt(unsigned long long _val) { if (_val == 0) { val.push_back(0); return; } while (_val) { val.push_back(_val % 10); _val /= 10; } val = vector<value_type>(val.rbegin(), val.rend()); } UnsignedBigInt::UnsignedBigInt(const vector<value_type>& _val) : val(_val) {} UnsignedBigInt::UnsignedBigInt(const vector<value_type>&& _val) : val(_val) {} //绫诲瀷杞崲鍑芥暟 UnsignedBigInt::operator string() const { string ans; for (size_type i = 0, len = val.size(); i < len; i++) { ans += char(val[i] + '0'); } return ans; } //鏅€氬嚱鏁? const UnsignedBigInt UnsignedBigInt::factorial() const { UnsignedBigInt ans(1U); for (UnsignedBigInt i = 2; i <= (*this); ++i) { ans *= i; } return ans; } const UnsignedBigInt::maxinteger_type UnsignedBigInt::value() const { UnsignedBigInt::maxinteger_type ans = 0; for (auto it = val.rbegin(); it != val.rend(); ++it) { ans = ans * 10 + *it; } return ans; } //閲嶈浇绠楁湳杩愮畻绗? const UnsignedBigInt UnsignedBigInt::operator+(const UnsignedBigInt& a) const { if ((*this) > a) return a + (*this); UnsignedBigInt ans; size_type lena = val.size(), lenb = a.val.size(), x = 0; // lena<=lenb ans.val.pop_back(); for (size_type i = 0; i < lenb; i++) { if (i >= lena) ans.val.push_back(a.val[lenb - i - 1] + x); else ans.val.push_back(val[lena - i - 1] + a.val[lenb - i - 1] + x); x = ans.val[i] / 10; ans.val[i] %= 10; } if (x) { ans.val.push_back(x); } while (ans.val.size() && ans.val.back() == 0) { ans.val.pop_back(); } if (ans.val.empty()) { ans.val.push_back(0); } ans.val = vector<value_type>(ans.val.rbegin(), ans.val.rend()); return ans; } const UnsignedBigInt UnsignedBigInt::operator+(const UnsignedBigInt&& a) const { if ((*this) > a) return a + (*this); UnsignedBigInt ans; size_type lena = val.size(), lenb = a.val.size(), x = 0; // lena<=lenb ans.val.pop_back(); for (size_type i = 0; i < lenb; i++) { if (i >= lena) ans.val.push_back(a.val[lenb - i - 1] + x); else ans.val.push_back(val[lena - i - 1] + a.val[lenb - i - 1] + x); x = ans.val[i] / 10; ans.val[i] %= 10; } if (x) { ans.val.push_back(x); } while (ans.val.size() && ans.val.back() == 0) { ans.val.pop_back(); } if (ans.val.empty()) { ans.val.push_back(0); } ans.val = vector<value_type>(ans.val.rbegin(), ans.val.rend()); return ans; } const UnsignedBigInt UnsignedBigInt::operator-(const UnsignedBigInt& a) const { if ((*this) < a) { cerr << "const UnsignedBigInt UnsignedBigInt::operator-(const " "UnsignedBigInt& a) const:(*this)<a not alivible!\n"; throw exception(); return UnsignedBigInt(); } UnsignedBigInt ans; size_type lena = val.size(), lenb = a.val.size(), x = 0; // lena>=lenb for (int i = 0; i < lena; i++) { std::make_signed<value_type>::type tmp; if (i >= lenb) tmp = val[lena - i - 1] - x; else tmp = val[lena - i - 1] - a.val[lenb - i - 1] - x; if (tmp < 0) { x = 1; ans.val.push_back(static_cast<value_type>(tmp + 10)); } else { x = 0; ans.val.push_back(static_cast<value_type>(tmp)); } } while (ans.val.size() && ans.val.back() == 0) { ans.val.pop_back(); } if (ans.val.empty()) { return 0U; } else { ans.val = vector<value_type>(ans.val.rbegin(), ans.val.rend() - 1); return ans; } } const UnsignedBigInt UnsignedBigInt::operator-(const UnsignedBigInt&& a) const { if ((*this) < a) { cerr << "const UnsignedBigInt UnsignedBigInt::operator-(const " "UnsignedBigInt&& a) const:(*this)<a not alivible!\n"; throw exception(); return UnsignedBigInt(); } UnsignedBigInt ans; size_type lena = val.size(), lenb = a.val.size(), x = 0; // lena>=lenb for (int i = 0; i < lena; i++) { std::make_signed<value_type>::type tmp; if (i >= lenb) tmp = val[lena - i - 1] - x; else tmp = val[lena - i - 1] - a.val[lenb - i - 1] - x; if (tmp < 0) { x = 1; ans.val.push_back(static_cast<value_type>(tmp + 10)); } else { x = 0; ans.val.push_back(static_cast<value_type>(tmp)); } } while (ans.val.size() && ans.val.back() == 0) { ans.val.pop_back(); } if (ans.val.empty()) { return 0U; } else { ans.val = vector<value_type>(ans.val.rbegin(), ans.val.rend() - 1); return ans; } } const UnsignedBigInt UnsignedBigInt::operator*(const UnsignedBigInt& a) const { UnsignedBigInt ans; size_type lena = val.size(), lenb = a.val.size(), x = 0; for (size_type i = 0, len = lena + lenb; i < len; i++) { ans.val.push_back(0U); } for (size_type i = 0; i < lena; i++) { x = 0; for (size_type j = 0; j < lenb; j++) { ans.val[i + j] += val[lena - i - 1] * a.val[lenb - j - 1] + x; x = ans.val[i + j] / 10; ans.val[i + j] %= 10; } for (size_type j = 0; x; j++) { if (ans.val.size() > i + lenb + j) { ans.val[i + j + lenb] += x % 10; x = ans.val[i + j + lenb] / 10; ans.val[i + j + lenb] %= 10; } else { while (x) { ans.val.push_back(x % 10); x /= 10; } break; } } } while (ans.val.size() && *(ans.val.end() - 1) == 0) { ans.val.pop_back(); } if (ans.val.empty()) { ans.val.push_back(0); } ans.val = vector<value_type>(ans.val.rbegin(), ans.val.rend()); return ans; } const UnsignedBigInt UnsignedBigInt::operator*(const UnsignedBigInt&& a) const { UnsignedBigInt ans; size_type lena = val.size(), lenb = a.val.size(), x = 0; for (size_type i = 0, len = lena + lenb; i < len; i++) { ans.val.push_back(0U); } for (size_type i = 0; i < lena; i++) { x = 0; for (size_type j = 0; j < lenb; j++) { ans.val[i + j] += val[lena - i - 1] * a.val[lenb - j - 1] + x; x = ans.val[i + j] / 10; ans.val[i + j] %= 10; } for (size_type j = 0; x; j++) { if (ans.val.size() > i + lenb + j) { ans.val[i + j + lenb] += x % 10; x = ans.val[i + j + lenb] / 10; ans.val[i + j + lenb] %= 10; } else { while (x) { ans.val.push_back(x % 10); x /= 10; } break; } } } while (ans.val.size() && *(ans.val.end() - 1) == 0) { ans.val.pop_back(); } if (ans.val.empty()) { ans.val.push_back(0); } ans.val = vector<value_type>(ans.val.rbegin(), ans.val.rend()); return ans; } const UnsignedBigInt UnsignedBigInt::operator/(const UnsignedBigInt& a) const { if (a == 0U) { //涓嶈兘闄や互0 cerr << "const UnsignedBigInt UnsignedBigInt::operator/(const " "UnsignedBigInt& a) const:Cannot with zero!\n"; throw exception(); return UnsignedBigInt(); } else if (a == 1U) { //闄や互1杩斿洖鑷韩 return (*this); } UnsignedBigInt ans, t(*this), t2(a); ans.val.pop_back(); while (t2 <= t) { t2.val.push_back(0); } while (t >= a) { t2.val.pop_back(); ans.val.push_back(0); while (t >= t2) { t -= t2; ++ans.val[ans.val.size() - 1]; } } while (t2 > a) { ans.val.push_back(0); t2.val.pop_back(); } if (ans.val.empty()) { ans.val.push_back(0); } return ans; } const UnsignedBigInt UnsignedBigInt::operator/(const UnsignedBigInt&& a) const { if (a == 0U) { //涓嶈兘闄や互0 cerr << "const UnsignedBigInt UnsignedBigInt::operator/(const " "UnsignedBigInt&& a) const:Cannot with zero!\n"; throw exception(); return UnsignedBigInt(); } else if (a == 1U) { //闄や互1杩斿洖鑷韩 return (*this); } UnsignedBigInt ans, t(*this), t2(a); ans.val.pop_back(); while (t2 <= t) { t2.val.push_back(0); } while (t >= a) { t2.val.pop_back(); ans.val.push_back(0); while (t >= t2) { t -= t2; ++ans.val[ans.val.size() - 1]; } } while (t2 > a) { ans.val.push_back(0); t2.val.pop_back(); } if (ans.val.empty()) { ans.val.push_back(0); } return ans; } const UnsignedBigInt UnsignedBigInt::operator%(const UnsignedBigInt& a) const { if (a == 0U) { //涓嶈兘瀵?鍙栦綑 cerr << "const UnsignedBigInt UnsignedBigInt::operator%(const " "UnsignedBigInt& a) const:Cannot with zero!\n"; throw exception(); return UnsignedBigInt(); } else if (a == 1U) { //浠讳綍鏁?1灏辨槸0 return 0; } UnsignedBigInt t(*this), t2(a); while (t2 <= t) { t2.val.push_back(0); } while (t >= a) { t2.val.pop_back(); while (t >= t2) { t -= t2; } } return t; } const UnsignedBigInt UnsignedBigInt::operator%(const UnsignedBigInt&& a) const { if (a == 0U) { //涓嶈兘瀵?鍙栦綑 cerr << "const UnsignedBigInt UnsignedBigInt::operator%(const " "UnsignedBigInt&& a) const:Cannot with zero!\n"; throw exception(); return UnsignedBigInt(); } else if (a == 1U) { //浠讳綍鏁?1灏辨槸0 return 0; } UnsignedBigInt t(*this), t2(a); while (t2 <= t) { t2.val.push_back(0); } while (t >= a) { t2.val.pop_back(); while (t >= t2) { t -= t2; } } return t; } const UnsignedBigInt UnsignedBigInt::operator^(const UnsignedBigInt::maxinteger_type& a) const { if (a == 0U) return 1U; else if (a == 1U) return (*this); else { UnsignedBigInt::maxinteger_type cnt = a; UnsignedBigInt s((*this)), ans(1); while (cnt) { if (cnt & 1) { ans *= s; } s *= s; cnt >>= 1; } return ans; } } const UnsignedBigInt UnsignedBigInt::operator^(const UnsignedBigInt::maxinteger_type&& a) const { if (a == 0U) return 1U; else if (a == 1U) return (*this); else { UnsignedBigInt::maxinteger_type cnt = a; UnsignedBigInt s((*this)), ans(1); while (cnt) { if (cnt & 1) { ans *= s; } s *= s; cnt >>= 1; } return ans; } } //閲嶈浇姣旇緝杩愮畻绗? bool UnsignedBigInt::operator<(const UnsignedBigInt& a) const { size_type lena = val.size(), lenb = a.val.size(); if (lena < lenb) return true; else if (lena > lenb) return false; else { for (size_type i = 0; i < lena; i++) { if (val[i] < a.val[i]) return true; else if (val[i] > a.val[i]) return false; } return false; } } bool UnsignedBigInt::operator<=(const UnsignedBigInt& a) const { size_type lena = val.size(), lenb = a.val.size(); if (lena < lenb) return true; else if (lena > lenb) return false; else { for (size_type i = 0; i < lena; i++) { if (val[i] < a.val[i]) return true; else if (val[i] > a.val[i]) return false; } return true; } } bool UnsignedBigInt::operator==(const UnsignedBigInt& a) const { size_type lena = val.size(), lenb = a.val.size(); if (lena != lenb) return false; else { for (size_type i = 0; i < lena; i++) { if (val[i] != a.val[i]) return false; } return true; } } //杈撳叆娴佽繍绠楃 istream& operator>>(istream& is, UnsignedBigInt& a) { string tmp; is >> tmp; try { a = tmp; } catch (...) { cerr << "istream& operator>>(istream& is, UnsignedBigInt& " "a):Something wrong!\n"; is.exceptions(std::istream::failbit); } return is; } istream& operator>>(istream& is, UnsignedBigInt&& a) { string tmp; is >> tmp; try { a = tmp; } catch (...) { cerr << "istream& operator>>(istream& is, UnsignedBigInt&& " "a):Something wrong!\n"; is.exceptions(std::istream::failbit); } return is; } // BigInt绫? //鏋勯€犲嚱鏁?瑙f瀽鍑芥暟 BigInt::BigInt() : sign(false) { // pass } BigInt::BigInt(string& s) : sign(false) { if (s[0] == '-') { //璐熸暟 sign = true; s.erase(s.begin()); } val = s; } BigInt::BigInt(string&& s) : sign(false) { if (s[0] == '-') { //璐熸暟 sign = true; s.erase(s.begin()); } val = s; } BigInt::BigInt(long long _val) { if (_val >= 0) { val = _val; } else { sign = true; val = -_val; } } BigInt::BigInt(const UnsignedBigInt& _val) : val(_val), sign(false) {} BigInt::BigInt(UnsignedBigInt&& _val) : val(_val), sign(false) {} //绫诲瀷杞崲鍑芥暟 BigInt::operator string() const { return (sign ? "-" : "") + string(val); } BigInt::operator UnsignedBigInt() const { if (sign) { cerr << "BigInt::operator UnsignedBigInt() const:Cannot give class " "UnsignedBigInt a negative number!\n"; throw exception(); return UnsignedBigInt(); } return val; } //鏅€氬嚱鏁? bool BigInt::isnegative() const { return !sign; } const BigInt BigInt::factorial() const { if (sign) { cerr << "const BigInt BigInt::factorial() const:The factorial of a " "negative integer is undefined!\n"; throw exception(); return 0LL; } return val.factorial(); } //閲嶈浇绠楁湳杩愮畻绗? const BigInt BigInt::operator-() const { BigInt ans; ans.sign = !sign; ans.val = val; return ans; } const BigInt BigInt::operator+(const BigInt& a) const { switch ((sign << 1) | a.sign) { case 0: //閮芥槸姝f暟锛岀粷瀵瑰€肩浉鍔? return (val + a.val); case 1: //鑷繁鏄鏁帮紝a鏄礋鏁帮紝绛変环浜?*this)-a.val return (val - a.val); case 2: //鑷繁鏄礋鏁帮紝a鏄鏁帮紝绛変环浜巃-(*this).val return (a.val - val); case 3: //閮芥槸璐熸暟锛岀粷瀵瑰€肩浉鍔犲悗鍙栬礋 return -BigInt((val + a.val)); } return BigInt(); } const BigInt BigInt::operator+(const BigInt&& a) const { switch ((sign << 1) | a.sign) { case 0: //閮芥槸姝f暟锛岀粷瀵瑰€肩浉鍔? return (val + a.val); case 1: //鑷繁鏄鏁帮紝a鏄礋鏁帮紝绛変环浜?*this)-a.val return (val - a.val); case 2: //鑷繁鏄礋鏁帮紝a鏄鏁帮紝绛変环浜巃-(*this).val return (a.val - val); case 3: //閮芥槸璐熸暟锛岀粷瀵瑰€肩浉鍔犲悗鍙栬礋 return -BigInt((val + a.val)); } return BigInt(); } const BigInt BigInt::operator-(const BigInt& a) const { switch ((sign << 1) | a.sign) { case 0: //閮芥槸姝f暟锛岀粷瀵瑰€肩浉鍑忥紝娉ㄦ剰鐩稿噺鍚庡皬浜?鐨勬儏鍐? if (val < a.val) { return -BigInt(a.val - val); } else { return (val - a.val); } case 1: //鑷繁鏄鏁帮紝a鏄礋鏁帮紝绛変环浜?*this)+a.val return (val + a.val); case 2: //鑷繁鏄礋鏁帮紝a鏄鏁帮紝绛変环浜?(a.val+(*this)) return -BigInt(a.val + val); case 3: //閮芥槸璐熸暟锛岀瓑浠蜂簬(a.val-(*this)),鍚屾牱娉ㄦ剰鐩稿噺鍚庡皬浜?鐨勬儏鍐? if (val <= a.val) { return (a.val - val); } else { return -BigInt(val - a.val); } } return BigInt(); } const BigInt BigInt::operator-(const BigInt&& a) const { switch ((sign << 1) | a.sign) { case 0: //閮芥槸姝f暟锛岀粷瀵瑰€肩浉鍑忥紝娉ㄦ剰鐩稿噺鍚庡皬浜?鐨勬儏鍐? if (val < a.val) { return -BigInt(a.val - val); } else { return (val - a.val); } case 1: //鑷繁鏄鏁帮紝a鏄礋鏁帮紝绛変环浜?*this)+a.val return (val + a.val); case 2: //鑷繁鏄礋鏁帮紝a鏄鏁帮紝绛変环浜?(a.val+(*this)) return -BigInt(a.val + val); case 3: //閮芥槸璐熸暟锛岀瓑浠蜂簬(a.val-(*this)),鍚屾牱娉ㄦ剰鐩稿噺鍚庡皬浜?鐨勬儏鍐? if (val <= a.val) { return (a.val - val); } else { return -BigInt(val - a.val); } } return BigInt(); } const BigInt BigInt::operator*(const BigInt& a) const { //寮傛垨杩愮畻瑙勫垯锛氱浉鍚屼负false锛屼笉鍚屼负true if (a.sign ^ sign) return -BigInt( val * a.val); //涓嶅悓绗﹀彿锛屼竴瀹氭湁涓€涓槸璐熷彿锛屾墍浠ユ槸缁濆鍊肩浉涔樺啀鍙栬礋 else return val * a.val; //鐩稿悓绗﹀彿锛岃涔堟姝e緱姝o紝瑕佷箞璐熻礋寰楁锛岄兘鏄粷瀵瑰€肩浉涔? } const BigInt BigInt::operator*(const BigInt&& a) const { //寮傛垨杩愮畻瑙勫垯锛氱浉鍚屼负false锛屼笉鍚屼负true if (a.sign ^ sign) return -BigInt( val * a.val); //涓嶅悓绗﹀彿锛屼竴瀹氭湁涓€涓槸璐熷彿锛屾墍浠ユ槸缁濆鍊肩浉涔樺啀鍙栬礋 else return val * a.val; //鐩稿悓绗﹀彿锛岃涔堟姝e緱姝o紝瑕佷箞璐熻礋寰楁锛岄兘鏄粷瀵瑰€肩浉涔? } const BigInt BigInt::operator/(const BigInt& a) const { //寮傛垨杩愮畻瑙勫垯锛氱浉鍚屼负false锛屼笉鍚屼负true if (a.sign ^ sign) return -BigInt( val / a.val); //涓嶅悓绗﹀彿锛屼竴瀹氭湁涓€涓槸璐熷彿锛屾墍浠ユ槸缁濆鍊肩浉闄ゅ啀鍙栬礋 else return val / a.val; //鐩稿悓绗﹀彿锛岀鍙蜂細浜掔浉鎶垫秷锛屾墍浠ユ槸缁濆鍊肩浉闄? } const BigInt BigInt::operator/(const BigInt&& a) const { //寮傛垨杩愮畻瑙勫垯锛氱浉鍚屼负false锛屼笉鍚屼负true if (a.sign ^ sign) return -BigInt( val / a.val); //涓嶅悓绗﹀彿锛屼竴瀹氭湁涓€涓槸璐熷彿锛屾墍浠ユ槸缁濆鍊肩浉闄ゅ啀鍙栬礋 else return val / a.val; //鐩稿悓绗﹀彿锛岀鍙蜂細浜掔浉鎶垫秷锛屾墍浠ユ槸缁濆鍊肩浉闄? } const BigInt BigInt::operator%(const BigInt& a) const { switch ((sign << 1) | a.sign) { case 0: //閮芥槸姝f暟 return val % a.val; case 1: //鑷繁鏄鏁帮紝a鏄礋鏁? return -BigInt(a.val - val % a.val); case 2: //鑷繁鏄礋鏁帮紝a鏄鏁? return a.val - val % a.val; case 3: //閮芥槸璐熸暟 return -BigInt(val % a.val); } return BigInt(); } const BigInt BigInt::operator%(const BigInt&& a) const { switch ((sign << 1) | a.sign) { case 0: //閮芥槸姝f暟 return val % a.val; case 1: //鑷繁鏄鏁帮紝a鏄礋鏁? return -BigInt(a.val - val % a.val); case 2: //鑷繁鏄礋鏁帮紝a鏄鏁? return a.val - val % a.val; case 3: //閮芥槸璐熸暟 return -BigInt(val % a.val); } return BigInt(); } const BigInt BigInt::operator^(const BigInt::maxinteger_type& a) const { if (a < 0) { //濡傛灉a涓鸿礋鏁? return 0; //浠讳綍鏁扮殑灏忎簬0鐨勬鏂归兘灏忎簬1锛屽拷鐣? } else if (a & sign) { //濡傛灉a涓哄鏁拌€屼笖sign鏄痶rue锛堣礋鏁帮級 return -BigInt(val ^ a); } else { //姝f暟鐨勫箓娆℃柟閮芥槸姝f暟锛岃礋鏁扮殑鍋舵暟骞傛鏂逛篃鏄鏁帮紙寰堟槑鏄撅紝璐熻礋寰楁锛? return (val ^ a); } } const BigInt BigInt::operator^(const BigInt::maxinteger_type&& a) const { if (a < 0) { //濡傛灉a涓鸿礋鏁? return 0; //浠讳綍鏁扮殑灏忎簬0鐨勬鏂归兘灏忎簬1锛屽拷鐣? } else if (a & sign) { //濡傛灉a涓哄鏁拌€屼笖sign鏄痶rue锛堣礋鏁帮級 return -BigInt(val ^ a); } else { //姝f暟鐨勫箓娆℃柟閮芥槸姝f暟锛岃礋鏁扮殑鍋舵暟骞傛鏂逛篃鏄鏁帮紙寰堟槑鏄撅紝璐熻礋寰楁锛? return (val ^ a); } } //閲嶈浇姣旇緝杩愮畻绗? bool BigInt::operator<(const BigInt& a) const { if (sign < a.sign) return false; //鑷繁姝璐燂紝(*this)>a else if (sign > a.sign) return true; //鑷繁璐焌姝o紝(*this)<a else if (sign) { //璐熸暟姣斿ぇ灏忥細璋佺殑缁濆鍊煎皬璋佸ぇ return val > a.val; } else { //姝f暟姣斿ぇ灏忥細璋佹墦缁濆鍊煎ぇ璋佸ぇ return val < a.val; } } bool BigInt::operator<(const BigInt&& a) const { if (sign < a.sign) return false; //鑷繁姝璐燂紝(*this)>a else if (sign > a.sign) return true; //鑷繁璐焌姝o紝(*this)<a else if (sign) { //璐熸暟姣斿ぇ灏忥細璋佺殑缁濆鍊煎皬璋佸ぇ return val > a.val; } else { //姝f暟姣斿ぇ灏忥細璋佹墦缁濆鍊煎ぇ璋佸ぇ return val < a.val; } } bool BigInt::operator<=(const BigInt& a) const { if (sign < a.sign) return false; //鑷繁姝璐燂紝(*this)>a else if (sign > a.sign) return true; //鑷繁璐焌姝o紝(*this)<a else if (sign) { //璐熸暟姣斿ぇ灏忥細璋佺殑缁濆鍊煎皬璋佸ぇ return val >= a.val; } else { //姝f暟姣斿ぇ灏忥細璋佹墦缁濆鍊煎ぇ璋佸ぇ return val <= a.val; } } bool BigInt::operator<=(const BigInt&& a) const { if (sign < a.sign) return false; //鑷繁姝璐燂紝(*this)>a else if (sign > a.sign) return true; //鑷繁璐焌姝o紝(*this)<a else if (sign) { //璐熸暟姣斿ぇ灏忥細璋佺殑缁濆鍊煎皬璋佸ぇ return val >= a.val; } else { //姝f暟姣斿ぇ灏忥細璋佹墦缁濆鍊煎ぇ璋佸ぇ return val <= a.val; } } bool BigInt::operator==(const BigInt& a) const { //寮傛垨杩愮畻瑙勫垯锛氱浉鍚屼负false锛屼笉鍚屼负true if (!(sign ^ a.sign)) return false; //绗﹀彿涓嶄竴鏍凤紝鍊间竴瀹氫笉涓€鏍? else return val == a.val; //鍚﹀垯杩斿洖缁濆鍊兼槸鍚︿竴鏍? } bool BigInt::operator==(const BigInt&& a) const { //寮傛垨杩愮畻瑙勫垯锛氱浉鍚屼负false锛屼笉鍚屼负true if (!(sign ^ a.sign)) return false; //绗﹀彿涓嶄竴鏍凤紝鍊间竴瀹氫笉涓€鏍? else return val == a.val; //鍚﹀垯杩斿洖缁濆鍊兼槸鍚︿竴鏍? } //杈撳叆娴佽繍绠楃 istream& operator>>(istream& is, BigInt& a) { string tmp; is >> tmp; try { a = tmp; } catch (...) { cerr << "istream& operator>>(istream& is, BigInt& a):Something wrong!\n"; is.exceptions(std::istream::failbit); } return is; } istream& operator>>(istream& is, BigInt&& a) { string tmp; is >> tmp; try { a = tmp; } catch (...) { cerr << "istream& operator>>(istream& is, BigInt&& a):Something " "wrong!\n"; is.exceptions(std::istream::failbit); } return is; } #endif #include<iostream> using namespace std; int main(){ BigInt a,b; cin >> a >> b; cout << a+b; return 0; }
对了,注释乱码了,见谅~
为什么代码会这么多呢?因为我把高精度的大部分算法都放里面了,900多行当然多啊。
信息
- ID
- 6800
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 1
- 标签
- 递交数
- 766
- 已通过
- 292
- 上传者