1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160
| #include <iostream> #include <fstream> #include <vector> using namespace std; struct BigIntTiny { int sign; std::vector<int> v;
BigIntTiny() : sign(1) {} BigIntTiny(const std::string &s) { *this = s; } BigIntTiny(int v) { char buf[21]; sprintf(buf, "%d", v); *this = buf; } void zip(int unzip) { if(unzip == 0) { for(int i = 0; i < (int)v.size(); i++) v[i] = get_pos(i * 4) + get_pos(i * 4 + 1) * 10 + get_pos(i * 4 + 2) * 100 + get_pos(i * 4 + 3) * 1000; } else for(int i = (v.resize(v.size() * 4), (int)v.size() - 1), a; i >= 0; i--) a = (i % 4 >= 2) ? v[i / 4] / 100 : v[i / 4] % 100, v[i] = (i & 1) ? a / 10 : a % 10; setsign(1, 1); } int get_pos(unsigned pos) const { return pos >= v.size() ? 0 : v[pos]; } BigIntTiny &setsign(int newsign, int rev) { for(int i = (int)v.size() - 1; i > 0 && v[i] == 0; i--) v.erase(v.begin() + i); sign = (v.size() == 0 || (v.size() == 1 && v[0] == 0)) ? 1 : (rev ? newsign *sign : newsign); return *this; } std::string to_str() const { BigIntTiny b = *this; std::string s; for(int i = (b.zip(1), 0); i < (int)b.v.size(); ++i) s += char(*(b.v.rbegin() + i) + '0'); return (sign < 0 ? "-" : "") + (s.empty() ? std::string("0") : s); } bool absless(const BigIntTiny &b) const { if(v.size() != b.v.size()) return v.size() < b.v.size(); for(int i = (int)v.size() - 1; i >= 0; i--) if(v[i] != b.v[i]) return v[i] < b.v[i]; return false; } BigIntTiny operator-() const { BigIntTiny c = *this; c.sign = (v.size() > 1 || v[0]) ? -c.sign : 1; return c; } BigIntTiny &operator=(const std::string &s) { if(s[0] == '-') *this = s.substr(1); else { for(int i = (v.clear(), 0); i < (int)s.size(); ++i) v.push_back(*(s.rbegin() + i) - '0'); zip(0); } return setsign(s[0] == '-' ? -1 : 1, sign = 1); } bool operator<(const BigIntTiny &b) const { return sign != b.sign ? sign < b.sign : (sign == 1 ? absless(b) : b.absless(*this)); } bool operator==(const BigIntTiny &b) const { return v == b.v && sign == b.sign; } BigIntTiny &operator+=(const BigIntTiny &b) { if(sign != b.sign) return *this = (*this) - -b; v.resize(std::max(v.size(), b.v.size()) + 1); for(int i = 0, carry = 0; i < (int)b.v.size() || carry; i++) { carry += v[i] + b.get_pos(i); v[i] = carry % 10000, carry /= 10000; } return setsign(sign, 0); } BigIntTiny operator+(const BigIntTiny &b) const { BigIntTiny c = *this; return c += b; } void add_mul(const BigIntTiny &b, int mul) { v.resize(std::max(v.size(), b.v.size()) + 2); for(int i = 0, carry = 0; i < (int)b.v.size() || carry; i++) { carry += v[i] + b.get_pos(i) * mul; v[i] = carry % 10000, carry /= 10000; } } BigIntTiny operator-(const BigIntTiny &b) const { if(sign != b.sign) return (*this) + -b; if(absless(b)) return -(b - *this); BigIntTiny c; for(int i = 0, borrow = 0; i < (int)v.size(); i++) { borrow += v[i] - b.get_pos(i); c.v.push_back(borrow); c.v.back() -= 10000 * (borrow >>= 31); } return c.setsign(sign, 0); } BigIntTiny operator*(const BigIntTiny &b) const { if(b < *this) return b * *this; BigIntTiny c, d = b; for(int i = 0; i < (int)v.size(); i++, d.v.insert(d.v.begin(), 0)) c.add_mul(d, v[i]); return c.setsign(sign * b.sign, 0); } BigIntTiny operator/(const BigIntTiny &b) const { BigIntTiny c, d; d.v.resize(v.size()); double db = 1.0 / (b.v.back() + (b.get_pos((unsigned)b.v.size() - 2) / 1e4) + (b.get_pos((unsigned)b.v.size() - 3) + 1) / 1e8); for(int i = (int)v.size() - 1; i >= 0; i--) { c.v.insert(c.v.begin(), v[i]); int m = (int)((c.get_pos((int)b.v.size()) * 10000 + c.get_pos((int)b.v.size() - 1)) * db); c = c - b * m, d.v[i] += m; while(!(c < b)) c = c - b, d.v[i] += 1; } return d.setsign(sign * b.sign, 0); } BigIntTiny operator%(const BigIntTiny &b) const { return *this - *this / b * b; } bool operator>(const BigIntTiny &b) const { return b < *this; } bool operator<=(const BigIntTiny &b) const { return !(b < *this); } bool operator>=(const BigIntTiny &b) const { return !(*this < b); } bool operator!=(const BigIntTiny &b) const { return !(*this == b); } }; ifstream fin("max.in"); ofstream fout("max.out"); BigIntTiny res = 1; int n, m, arr[10010]; int main() { fin >> n; if(n <= 4) { fout << n << endl << n << endl; return 0; } for(int i = 2; n; i++) if(n >= i) n -= i, arr[++m] = i; else arr[++m] = n, n = 0; if(arr[m - 1] >= arr[m]) { for(int i = m - 1; i >= 1 && arr[m]; i--) arr[i]++, arr[m]--; m--; } for(int i = 1; i <= m; i++) cout << arr[i] << ' ', res = res * arr[i]; fout << endl << res.to_str() << endl; return 0; }
|