fork download
copy 
  1. //#pragma GCC optimize("O3", "unroll-loops")
  2. //#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
  3.  
  4. #include <bits/stdc++.h>
  5. #define ldb long double
  6. //#define double ldb
  7. #define db double
  8. #define unomap unordered_map
  9. #define unoset unordered_set
  10. #define endl '\n'
  11. #define str string
  12. #define strstr stringstream
  13. #define sz(a) (int)a.size()
  14. //#define ll long long
  15. typedef long long ll;
  16. //#define int ll
  17. #define pii pair <int, int>
  18. #define pll pair <ll, ll>
  19. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  20. #define ull unsigned ll
  21. #define fir first
  22. #define sec second
  23. #define idc cin.ignore()
  24. #define lb lower_bound
  25. #define ub upper_bound
  26. #define all(s) s.begin(), s.end()
  27. #define rev reverse
  28. #define gcd __gcd
  29. #define pushb push_back
  30. #define popb pop_back
  31. #define pushf push_front
  32. #define popf pop_front
  33. #define mul2x(a, x) a << x
  34. #define div2x(a, x) a >> x
  35. #define lcm(a, b) (a / __gcd(a, b) * b)
  36. #define log_base(x, base) log(x) / log(base)
  37. #define debug cerr << "No errors!"; exit(0);
  38. #define forw(i, a, b) for (int i = a; i <= b; ++i)
  39. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  40. #define fors(i, a, b) for (int i = a; i >= b; --i)
  41. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  42. #define pqueue priority_queue
  43. #define sqrt sqrtl
  44. #define i128 __int128
  45. #define popcount __builtin_popcountll
  46. #define BIT(x, i) (((x) >> (i)) & 1)
  47. #define MASK(x) ((1LL) << (x))
  48. #define want_digit(x) cout << fixed << setprecision(x);
  49. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  50. #define mapa make_pair
  51. using namespace std;
  52. const int MOD = 1e9 + 7; // 998244353
  53. const int inf = 1e9;
  54. const ll INF = 1e18;
  55. const int N = 2e5;
  56.  
  57. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  58. ll random(const ll &L, const ll &R) {
  59.     return uniform_int_distribution<ll> (L, R) (rng);
  60. }
  61.  
  62. namespace BigNum {
  63. //    typedef long long ll;
  64.     typedef long double ld;
  65.     typedef complex<ld> pt;
  66.     const int32_t MOD = 1e9 + 7;
  67.     const ld PI = acos(-1.L);
  68.  
  69.     template<class T> struct cplx {
  70.         T x, y;
  71.         cplx() {
  72.             x = 0.0;
  73.             y = 0.0;
  74.         }
  75.         cplx(T nx, T ny = 0) {
  76.             x = nx;
  77.             y = ny;
  78.         }
  79.         cplx operator+(const cplx &c) const {
  80.             return {x + c.x, y + c.y};
  81.         }
  82.         cplx operator-(const cplx &c) const {
  83.             return {x - c.x, y - c.y};
  84.         }
  85.         cplx operator*(const cplx &c) const {
  86.             return {x*c.x - y * c.y, x*c.y + y * c.x};
  87.         }
  88.         cplx& operator*=(const cplx &c) {
  89.             return *this = {x*c.x - y * c.y, x*c.y + y * c.x};
  90.         }
  91.         inline T real() const {
  92.             return x;
  93.         }
  94.         inline T imag() const {
  95.             return y;
  96.         }
  97.         // Only supports right scalar multiplication like p*c
  98.         template<class U> cplx operator*(const U &c) const {
  99.             return {x * c, y * c};
  100.         }
  101.         template<class U> cplx operator/(const U &c) const {
  102.             return {x / c, y / c};
  103.         }
  104.         template<class U> void operator/=(const U &c) {
  105.             x /= c;
  106.             y /= c;
  107.         }
  108.     };
  109.     #define polar(r,a)  (cplx<ld>){r*cos(a),r*sin(a)}
  110.  
  111.     const int32_t DIG = 9, FDIG = 4;
  112.     const int32_t BASE = 1e9, FBASE = 1e4;
  113.     typedef cplx<ld> Cplx;
  114.  
  115.  
  116.     // use mulmod when taking mod by int32_t v and v>2e9
  117.     // you can use mod by bigint in that case too
  118.     struct bigint {
  119.         int32_t sgn;
  120.         vector<int32_t> a;
  121.         bigint() : sgn(1) {}
  122.         bigint(ll v) {
  123.             *this = v;
  124.         }
  125.         bigint& operator = (ll v) {
  126.             sgn = 1;
  127.             if (v < 0) sgn = -1, v = -v;
  128.             a.clear();
  129.             for (; v > 0; v /= BASE) a.push_back(v % BASE);
  130.             return *this;
  131.         }
  132.         bigint(const bigint& other) {
  133.             sgn = other.sgn;
  134.             a = other.a;
  135.         }
  136.         friend void swap(bigint& a, bigint& b) {
  137.             swap(a.sgn, b.sgn);
  138.             swap(a.a, b.a);
  139.         }
  140.         bigint& operator = (bigint other) {
  141.             swap(*this, other);
  142.             return *this;
  143.         }
  144.         bigint(bigint&& other) : bigint() {
  145.             swap(*this, other);
  146.         }
  147.         bigint(const string& s) {
  148.             read(s);
  149.         }
  150.         void read(const string& s) {
  151.             sgn = 1;
  152.             a.clear();
  153.             int32_t k = 0;
  154.             for (; k < (int32_t) s.size() && (s[k] == '-' | s[k] == '+'); k++)
  155.                 if (s[k] == '-') sgn = -sgn;
  156.             for (int32_t i = s.size() - 1; i >= k; i -= DIG) {
  157.                 int32_t x = 0;
  158.                 for (int32_t j = max(k, i - DIG + 1); j <= i; j++) x = x * 10 + s[j] - '0';
  159.                 a.push_back(x);
  160.             }
  161.             trim();
  162.         }
  163.         friend istream& operator>>(istream &in, bigint &v) {
  164.             string s;
  165.             in >> s;
  166.             v.read(s);
  167.             return in;
  168.         }
  169.         friend ostream& operator<<(ostream &out, const bigint &v) {
  170.             if (v.sgn == -1 && !v.zero()) out << '-';
  171.             out << (v.a.empty() ? 0 : v.a.back());
  172.             for (int32_t i = (int32_t) v.a.size() - 2; i >= 0; --i)
  173.                 out << setw(DIG) << setfill('0') << v.a[i];
  174.             return out;
  175.         }
  176.         bool operator<(const bigint &v) const {
  177.             if (sgn != v.sgn) return sgn < v.sgn;
  178.             if (a.size() != v.a.size()) return a.size() * sgn < v.a.size() * v.sgn;
  179.             for (int32_t i = (int32_t)a.size() - 1; i >= 0; i--)
  180.                 if (a[i] != v.a[i]) return a[i] * sgn < v.a[i] * sgn;
  181.             return 0;
  182.         }
  183.         bool operator>(const bigint &v) const {
  184.             return v < *this;
  185.         }
  186.         bool operator<=(const bigint &v) const {
  187.             return !(v < *this);
  188.         }
  189.         bool operator>=(const bigint &v) const {
  190.             return !(*this < v);
  191.         }
  192.         bool operator==(const bigint &v) const {
  193.             return !(*this < v) && !(v < *this);
  194.         }
  195.         bool operator!=(const bigint &v) const {
  196.             return *this < v || v < *this;
  197.         }
  198.         friend int32_t __cmp(const bigint& x, const bigint& y) {
  199.             if (x.a.size() != y.a.size()) return x.a.size() < y.a.size() ? -1 : 1;
  200.             for (int32_t i = (int32_t) x.a.size() - 1; i >= 0; --i) if (x.a[i] != y.a[i])
  201.                     return x.a[i] < y.a[i] ? -1 : 1;
  202.             return 0;
  203.         }
  204.  
  205.         bigint operator-() const {
  206.             bigint res = *this;
  207.             if (zero()) return res;
  208.             res.sgn = -sgn;
  209.             return res;
  210.         }
  211.  
  212.         void __add(const bigint& v) {
  213.             if (a.size() < v.a.size()) a.resize(v.a.size(), 0);
  214.             for (int32_t i = 0, carry = 0; i < (int32_t) max(a.size(), v.a.size()) || carry; ++i) {
  215.                 if (i == (int32_t) a.size()) a.push_back(0);
  216.                 a[i] += carry + (i < (int32_t) v.a.size() ? v.a[i] : 0);
  217.                 carry = a[i] >= BASE;
  218.                 if (carry) a[i] -= BASE;
  219.             }
  220.         }
  221.  
  222.         void __sub(const bigint& v) {
  223.             for (int32_t i = 0, carry = 0; i < (int32_t) v.a.size() || carry; ++i) {
  224.                 a[i] -= carry + (i < (int32_t) v.a.size() ? v.a[i] : 0);
  225.                 carry = a[i] < 0;
  226.                 if (carry) a[i] += BASE;
  227.             }
  228.             this->trim();
  229.         }
  230.  
  231.         bigint operator+=(const bigint& v) {
  232.             if (sgn == v.sgn) __add(v);
  233.             else if (__cmp(*this, v) >= 0) __sub(v);
  234.             else {
  235.                 bigint vv = v;
  236.                 swap(*this, vv);
  237.                 __sub(vv);
  238.             }
  239.             return *this;
  240.         }
  241.  
  242.         bigint operator-=(const bigint& v) {
  243.             if (sgn == v.sgn) {
  244.                 if (__cmp(*this, v) >= 0) __sub(v);
  245.                 else {
  246.                     bigint vv = v;
  247.                     swap(*this, vv);
  248.                     __sub(vv);
  249.                     sgn = -sgn;
  250.                 }
  251.             } else __add(v);
  252.             return *this;
  253.         }
  254.  
  255.         template< typename L, typename R >
  256.         typename enable_if <
  257.         is_convertible<L, bigint>::value &&
  258.         is_convertible<R, bigint>::value &&
  259.         is_lvalue_reference < R&& >::value,
  260.         bigint >::type friend operator + (L&& l, R&& r) {
  261.             bigint result(forward<L>(l));
  262.             result += r;
  263.             return result;
  264.         }
  265.         template< typename L, typename R >
  266.         typename enable_if <
  267.         is_convertible<L, bigint>::value &&
  268.         is_convertible<R, bigint>::value &&
  269.         is_rvalue_reference < R&& >::value,
  270.         bigint >::type friend operator + (L&& l, R&& r) {
  271.             bigint result(move(r));
  272.             result += l;
  273.             return result;
  274.         }
  275.         template< typename L, typename R >
  276.         typename enable_if <
  277.         is_convertible<L, bigint>::value &&
  278.         is_convertible<R, bigint>::value,
  279.         bigint >::type friend operator - (L&& l, R&& r) {
  280.             bigint result(forward<L>(l));
  281.             result -= r;
  282.             return result;
  283.         }
  284.  
  285.         friend pair<bigint, bigint> divmod(const bigint& a1, const bigint& b1) {
  286.             ll norm = BASE / (b1.a.back() + 1);
  287.             bigint a = a1.abs() * norm, b = b1.abs() * norm, q = 0, r = 0;
  288.             q.a.resize(a.a.size());
  289.             for (int32_t i = a.a.size() - 1; i >= 0; i--) {
  290.                 r *= BASE;
  291.                 r += a.a[i];
  292.                 ll s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
  293.                 ll s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
  294.                 ll d = ((ll) BASE * s1 + s2) / b.a.back();
  295.                 r -= b * d;
  296.                 while (r < 0) r += b, --d;
  297.                 q.a[i] = d;
  298.             }
  299.             q.sgn = a1.sgn * b1.sgn;
  300.             r.sgn = a1.sgn;
  301.             q.trim();
  302.             r.trim();
  303.             auto res = make_pair(q, r / norm);
  304.             if (res.second < 0) res.second += b1;
  305.             return res;
  306.         }
  307.         bigint operator/(const bigint &v) const {
  308.             return divmod(*this, v).first;
  309.         }
  310.         bigint operator%(const bigint &v) const {
  311.             return divmod(*this, v).second;
  312.         }
  313.         void operator/=(int32_t v) {
  314.             if (llabs(v) >= BASE) {
  315.                 *this /= bigint(v);
  316.                 return;
  317.             }
  318.             if (v < 0) sgn = -sgn, v = -v;
  319.             for (int32_t i = (int32_t) a.size() - 1, rem = 0; i >= 0; --i) {
  320.                 ll cur = a[i] + rem * (ll)BASE;
  321.                 a[i] = (int32_t) (cur / v);
  322.                 rem = (int32_t) (cur % v);
  323.             }
  324.             trim();
  325.         }
  326.         bigint operator/(int32_t v) const {
  327.             if (llabs(v) >= BASE) return *this / bigint(v);
  328.             bigint res = *this;
  329.             res /= v;
  330.             return res;
  331.         }
  332.         void operator/=(const bigint &v) {
  333.             *this = *this / v;
  334.         }
  335.         ll operator%(ll v) const {
  336.             int32_t m = 0;
  337.             for (int32_t i = a.size() - 1; i >= 0; --i) m = (a[i] + m * (ll) BASE) % v;
  338.             return m * sgn;
  339.         }
  340.         void operator*=(int32_t v) {
  341.             if (llabs(v) >= BASE) {
  342.                 *this *= bigint(v);
  343.                 return;
  344.             }
  345.             if (v < 0) sgn = -sgn, v = -v;
  346.             for (int32_t i = 0, carry = 0; i < (int32_t) a.size() || carry; ++i) {
  347.                 if (i == (int32_t) a.size()) a.push_back(0);
  348.                 ll cur = a[i] * (ll) v + carry;
  349.                 carry = (int32_t) (cur / BASE);
  350.                 a[i] = (int32_t) (cur % BASE);
  351.             }
  352.             trim();
  353.         }
  354.         bigint operator*(int32_t v) const {
  355.             if (llabs(v) >= BASE) return *this * bigint(v);
  356.             bigint res = *this;
  357.             res *= v;
  358.             return res;
  359.         }
  360.  
  361.         static vector<int32_t> convert_base(const vector<int32_t> &a, int32_t old_digits, int32_t new_digits) {
  362.             vector<ll> p(max(old_digits, new_digits) + 1);
  363.             p[0] = 1;
  364.             for (int32_t i = 1; i < (int32_t) p.size(); i++)
  365.                 p[i] = p[i - 1] * 10;
  366.             vector<int32_t> res;
  367.             ll cur = 0;
  368.             int32_t cur_digits = 0;
  369.             for (int32_t i = 0; i < (int32_t) a.size(); i++) {
  370.                 cur += a[i] * p[cur_digits];
  371.                 cur_digits += old_digits;
  372.                 while (cur_digits >= new_digits) {
  373.                     res.push_back((ll)(cur % p[new_digits]));
  374.                     cur /= p[new_digits];
  375.                     cur_digits -= new_digits;
  376.                 }
  377.             }
  378.             res.push_back((int32_t) cur);
  379.             while (!res.empty() && !res.back())
  380.                 res.pop_back();
  381.             return res;
  382.         }
  383.  
  384.         void fft(vector<Cplx>& a, bool invert) const {
  385.             int32_t n = a.size();
  386.             for (int32_t i = 1, j = 0; i < n; ++i) {
  387.                 int32_t bit = n / 2;
  388.                 for (; j >= bit; bit /= 2) j -= bit;
  389.                 j += bit;
  390.                 if (i < j) swap(a[i], a[j]);
  391.             }
  392.             for (int32_t len = 2; len <= n; len *= 2) {
  393.                 ld ang = 2 * PI / len * (invert ? -1 : 1);
  394.                 Cplx wlen = polar(1, ang);
  395.                 for (int32_t i = 0; i < n; i += len) {
  396.                     Cplx w(1);
  397.                     for (int32_t j = 0; j < len / 2; ++j) {
  398.                         Cplx u = a[i + j], v = a[i + j + len / 2] * w;
  399.                         a[i + j] = u + v;
  400.                         a[i + j + len / 2] = u - v;
  401.                         w *= wlen;
  402.                     }
  403.                 }
  404.             }
  405.             if (invert) for (int32_t i = 0; i < n; ++i) a[i] /= n;
  406.         }
  407.         void multiply_fft(const vector<int32_t> &a, const vector<int32_t> &b, vector<int32_t> &res) const {
  408.             vector<Cplx> fa(a.begin(), a.end()), fb(b.begin(), b.end());
  409.             int32_t n = 1;
  410.             while (n < (int32_t) max(a.size(), b.size())) n *= 2;
  411.             n *= 2;
  412.             fa.resize(n);
  413.             fb.resize(n);
  414.             fft(fa, 0);
  415.             fft(fb, 0);
  416.             for (int32_t i = 0; i < n; ++i) fa[i] *= fb[i];
  417.             fft(fa, 1);
  418.             res.resize(n);
  419.             ll carry = 0;
  420.             for (int32_t i = 0; i < n; i++) {
  421.                 ll t = (ll)(fa[i].real() + 0.5) + carry;
  422.                 carry = t / FBASE;
  423.                 res[i] = t % FBASE;
  424.             }
  425.         }
  426.         static inline int32_t rev_incr(int32_t a, int32_t n) {
  427.             int32_t msk = n / 2, cnt = 0;
  428.             while ( a & msk ) {
  429.                 cnt++;
  430.                 a <<= 1;
  431.             }
  432.             a &= msk - 1;
  433.             a |= msk;
  434.             while ( cnt-- ) a >>= 1;
  435.             return a;
  436.         }
  437.         static vector<Cplx> FFT(vector<Cplx> v, int32_t dir = 1) {
  438.             Cplx wm, w, u, t;
  439.             int32_t n = v.size();
  440.             vector<Cplx> V(n);
  441.             for (int32_t k = 0, a = 0; k < n; ++k, a = rev_incr(a, n))
  442.                 V[a] = v[k] / ld(dir > 0 ? 1 : n);
  443.             for (int32_t m = 2; m <= n; m <<= 1) {
  444.                 wm = polar( (ld)1, dir * 2 * PI / m );
  445.                 for (int32_t k = 0; k < n; k += m) {
  446.                     w = 1;
  447.                     for (int32_t j = 0; j < m / 2; ++j, w *= wm) {
  448.                         u = V[k + j];
  449.                         t = w * V[k + j + m / 2];
  450.                         V[k + j] = u + t;
  451.                         V[k + j + m / 2] = u - t;
  452.                     }
  453.                 }
  454.             }
  455.             return V;
  456.         }
  457.         static void convolution(const vector<int32_t>& a, const vector<int32_t>& b, vector<int32_t>& c) {
  458.             int32_t sz = a.size() + b.size() - 1;
  459.             int32_t n  = 1 << int32_t(ceil(log2(sz)));
  460.             vector<Cplx> av(n, 0), bv(n, 0), cv;
  461.             for (int32_t i = 0; i < (int32_t) a.size(); i++) av[i] = a[i];
  462.             for (int32_t i = 0; i < (int32_t) b.size(); i++) bv[i] = b[i];
  463.             cv = FFT(bv);
  464.             bv = FFT(av);
  465.             for (int32_t i = 0; i < n; i++) av[i] = bv[i] * cv[i];
  466.             cv = FFT(av, -1);
  467.             c.resize(n);
  468.             ll carry = 0;
  469.             for (int32_t i = 0; i < n; i++) {
  470.                 ll t = ll(cv[i].real() + 0.5) + carry;
  471.                 carry = t / FBASE;
  472.                 c[i] = t % FBASE;
  473.             }
  474.         }
  475.         bigint mul_simple(const bigint &v) const {
  476.             bigint res;
  477.             res.sgn = sgn * v.sgn;
  478.             res.a.resize(a.size() + v.a.size());
  479.             for (int32_t i = 0; i < (int32_t) a.size(); i++) if (a[i])
  480.                     for (int32_t j = 0, carry = 0; j < (int32_t) v.a.size() || carry; j++) {
  481.                         ll cur = res.a[i + j] + (ll) a[i] * (j < (int32_t) v.a.size() ? v.a[j] : 0) + carry;
  482.                         carry = (int32_t) (cur / BASE);
  483.                         res.a[i + j] = (int32_t) (cur % BASE);
  484.                     }
  485.             res.trim();
  486.             return res;
  487.         }
  488.         bigint mul_fft(const bigint& v) const {
  489.             bigint res;
  490.             convolution(convert_base(a, DIG, FDIG), convert_base(v.a, DIG, FDIG), res.a);
  491.             res.a = convert_base(res.a, FDIG, DIG);
  492.             res.trim();
  493.             return res;
  494.         }
  495.         void operator*=(const bigint &v) {
  496.             *this = *this * v;
  497.         }
  498.         bigint operator*(const bigint &v) const {
  499.             if (1LL * a.size() * v.a.size() <= 1000111) return mul_simple(v);
  500.             return mul_fft(v);
  501.         }
  502.  
  503.         bigint abs() const {
  504.             bigint res = *this;
  505.             res.sgn *= res.sgn;
  506.             return res;
  507.         }
  508.         void trim() {
  509.             while (!a.empty() && !a.back()) a.pop_back();
  510.         }
  511.         bool zero() const {
  512.             return a.empty() || (a.size() == 1 && !a[0]);
  513.         }
  514.         friend bigint gcd(const bigint &a, const bigint &b) {
  515.             return b.zero() ? a : gcd(b, a % b);
  516.         }
  517.     };
  518.     bigint power(bigint a, ll k) {
  519.         bigint ans = 1;
  520.         while (k > 0) {
  521.             if (k & 1) ans *= a;
  522.             a *= a;
  523.             k >>= 1;
  524.         }
  525.         return ans;
  526.     }
  527. }
  528.  
  529. using BigNum :: bigint;
  530. using BigNum :: power;
  531.  
  532. bigint sq(bigint x) {
  533.     return x * x;
  534. }
  535.  
  536. bigint cb(bigint x) {
  537.     return x * x * x;
  538. }
  539.  
  540. ll n;
  541. bigint res;
  542. void solve() {
  543.     cin >> n;
  544.  
  545.     // Loại 1
  546.     bigint tmp = n;
  547.     res = tmp * (tmp + 1) / 2;
  548.  
  549.     // Loại 2
  550.     for (bigint i = 1; sq(i) <= n; i += 1) {
  551.         res += (sq(i) - sq(i - 1)) * i;
  552.     }
  553.     tmp = sqrt(n);
  554.     res += (tmp + 1) * (n - sq(tmp));
  555.  
  556.     // Loại 3
  557.     for (bigint i = 2; cb(i) <= n; i += 1) {
  558.         res += (cb(i) - cb(i - 1)) * (i - 1);
  559.     }
  560.     tmp = cbrt(n);
  561.     res += tmp * (n - cb(tmp) + 1);
  562.  
  563.     cout << res << endl;
  564. }
  565.  
  566. signed main() {
  567.     ios::sync_with_stdio(false), cin.tie(nullptr);
  568.     srand(time(NULL));
  569.     #define name "test"
  570.     if (fopen(name".INP", "r")) {
  571.         freopen(name".INP", "r", stdin);
  572.         freopen(name".OUT", "w", stdout);
  573.     }
  574.     bool testCase = false;
  575.     int numTest = 1;
  576. //    cin >> numTest;
  577.     forw (i, 1, numTest) {
  578.         if (testCase) cout << "Case " << i << ": ";
  579.         solve();
  580.     }
  581.     return 0;
  582. }
  583.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
2
stdout
copy 
8
https://ideone.com/ZFihy2
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!