• Source
    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.