結果
問題 |
No.8035 2018
|
ユーザー |
|
提出日時 | 2018-07-04 20:31:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 992 bytes |
コンパイル時間 | 1,622 ms |
コンパイル使用メモリ | 168,624 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 02:16:38 |
合計ジャッジ時間 | 2,204 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 7 |
ソースコード
#include <bits/stdc++.h> using namespace std; int count(int N) { int v = sqrt(N); vector<int> sc(v + 1), lc(v + 1); for (int i = 1; i <= v; ++i) sc[i] = i - 1; for (int i = 1; i <= v; ++i) lc[i] = N / i - 1; for (int p = 2; p <= v; ++p) if (sc[p] != sc[p - 1]) { int c = sc[p - 1]; int q = p * p; int w = v / p; for (int i = 1; i <= w; ++i) lc[i] -= lc[i * p] - c; int e = min(v, N / q); int m = N / p; for (int i = w + 1; i <= e; ++i) lc[i] -= sc[m / i] - c; for (int i = v; i >= q; --i) sc[i] -= sc[i / p] - c; } int ret = sc[int(cbrt(N))]; for (int p = 2; p <= v; ++p) if (sc[p] != sc[p - 1]) { ret += lc[p] - sc[p]; } return ret; } void solve() { int N; scanf("%d", &N); int hi = 1; for (; count(hi) < N; hi <<= 1); int lo = (hi >> 1) - 1; while (hi - lo > 1) { int mi = (lo + hi) >> 1; if (count(mi) < N) lo = mi; else hi = mi; } printf("%d\n", hi); } int main() { solve(); return 0; }