結果
問題 | No.1666 累乗数 |
ユーザー | Kude |
提出日時 | 2021-09-03 22:08:38 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 174 ms / 2,000 ms |
コード長 | 2,093 bytes |
コンパイル時間 | 4,183 ms |
コンパイル使用メモリ | 264,464 KB |
実行使用メモリ | 13,252 KB |
最終ジャッジ日時 | 2023-08-21 22:03:19 |
合計ジャッジ時間 | 8,804 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 170 ms
12,764 KB |
testcase_01 | AC | 174 ms
12,484 KB |
testcase_02 | AC | 173 ms
13,252 KB |
testcase_03 | AC | 171 ms
11,536 KB |
testcase_04 | AC | 172 ms
12,608 KB |
testcase_05 | AC | 173 ms
11,644 KB |
testcase_06 | AC | 173 ms
12,288 KB |
testcase_07 | AC | 172 ms
11,964 KB |
testcase_08 | AC | 172 ms
11,800 KB |
testcase_09 | AC | 173 ms
11,480 KB |
testcase_10 | AC | 174 ms
12,040 KB |
testcase_11 | AC | 174 ms
11,920 KB |
testcase_12 | AC | 173 ms
12,056 KB |
testcase_13 | AC | 174 ms
11,448 KB |
testcase_14 | AC | 174 ms
12,656 KB |
testcase_15 | AC | 174 ms
12,788 KB |
testcase_16 | AC | 174 ms
11,836 KB |
testcase_17 | AC | 174 ms
12,892 KB |
testcase_18 | AC | 173 ms
12,084 KB |
testcase_19 | AC | 173 ms
11,788 KB |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; #define rep(i,n)for (int i = 0; i < int(n); ++i) #define rrep(i,n)for (int i = int(n)-1; i >= 0; --i) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() template<class T> void chmax(T& a, const T& b) {a = max(a, b);} template<class T> void chmin(T& a, const T& b) {a = min(a, b);} using ll = long long; using P = pair<int,int>; using VI = vector<int>; using VVI = vector<VI>; using VL = vector<ll>; using VVL = vector<VL>; constexpr ll MX = 1000000000'000000000; bool is_square(ll x) { ll l = 1, r = 2; while(r * r <= x) l = r, r *= 2; while(r - l > 1) { ll c = (l + r) / 2; if (c * c <= x) l = c; else r = c; } return l * l == x; } int main() { ios::sync_with_stdio(false); cin.tie(0); VL d; for(int b = 3; b < 60; b++) { for(ll a = 2;; a++) { long long ab = 1; bool ok = true; rep(_, b) { if (ab > MX / a) { ok = false; break; } ab *= a; } if (!ok) break; if (!is_square(ab)) d.push_back(ab); } } sort(all(d)); d.erase(unique(all(d)), d.end()); // cout << d.size() << endl; // return 0; // rep(i, 10) cout << d[i] << " "; // cout << endl; int tt; cin >> tt; while(tt--) { int k; cin >> k; ll l = 1, r = 1000000001; while(r - l > 1) { ll c = (l + r) / 2; // # of <= c^2 ll cnt = c + (lower_bound(all(d), c * c) - d.begin()); if (cnt <= k) l = c; else r = c; } auto it = lower_bound(all(d), l * l); ll cnt = l + (it - d.begin()); int rest = k - cnt; // cout << l << ' ' << r << ' ' << rest << ' ' << (it - d.begin()) << endl; if (rest == 0) { cout << l * l << '\n'; } else { cout << it[rest - 1] << '\n'; } } }