結果
問題 |
No.8035 2018
|
ユーザー |
|
提出日時 | 2018-04-30 11:14:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 1,126 bytes |
コンパイル時間 | 1,596 ms |
コンパイル使用メモリ | 168,784 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-27 23:48:31 |
合計ジャッジ時間 | 2,244 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 7 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef unsigned u32; u32 count(u32 n) { if (n < 2) { return 0; } u32 v = sqrt(n); vector<u32> scnt(v + 1), lcnt(v + 1); for (u32 i = 1; i <= v; ++i) { scnt[i] = i - 1; } for (u32 i = 1; i <= v; ++i) { lcnt[i] = n / i - 1; } assert(lcnt[1] == n - 1); for (u32 p = 2; p <= v; ++p) { if (scnt[p] == scnt[p - 1]) { continue; } u32 q = p * p, c = scnt[p - 1]; u32 w = v / p, e = min(v, n / q), m = n / p; for (u32 i = 1; i <= w; ++i) { lcnt[i] -= lcnt[i * p] - c; } for (u32 i = w + 1; i <= e; ++i) { lcnt[i] -= scnt[m / i] - c; } for (u32 i = v; i >= q; --i) { scnt[i] -= scnt[i / p] - c; } } u32 ret = scnt[cbrt(n)]; for (u32 i = 2; i <= v; ++i) { if (scnt[i] != scnt[i - 1]) { ret += lcnt[i] - scnt[i]; } } return ret; } int main() { u32 n; scanf("%u", &n); u32 lo = 1, hi = 5150000; while (hi - lo > 1) { u32 mi = (lo + hi) >> 1; if (count(mi) < n) { lo = mi; } else { hi = mi; } } printf("%d\n", hi); return 0; }