結果
問題 | No.2526 Kth Not-divisible Number |
ユーザー | coindarw |
提出日時 | 2023-11-03 23:11:32 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,207 ms / 2,000 ms |
コード長 | 2,278 bytes |
コンパイル時間 | 4,360 ms |
コンパイル使用メモリ | 264,624 KB |
実行使用メモリ | 4,348 KB |
最終ジャッジ日時 | 2023-11-03 23:11:49 |
合計ジャッジ時間 | 15,877 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 1,129 ms
4,348 KB |
testcase_04 | AC | 1,130 ms
4,348 KB |
testcase_05 | AC | 1,126 ms
4,348 KB |
testcase_06 | AC | 1,132 ms
4,348 KB |
testcase_07 | AC | 1,137 ms
4,348 KB |
testcase_08 | AC | 1,173 ms
4,348 KB |
testcase_09 | AC | 1,147 ms
4,348 KB |
testcase_10 | AC | 1,172 ms
4,348 KB |
testcase_11 | AC | 1,207 ms
4,348 KB |
ソースコード
#ifdef ONLINE_JUDGE #include <bits/stdc++.h> #include <atcoder/all> #else #include <mylibs/all.h> #endif using ll = long long; using lll = __int128_t; #define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i) #define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i) #define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i) #define rreps(i, n) for (int i = ((int)(n)); i > 0; --i) #define rep2(i, s, n) for (int i = (s); i < (int)(n); i++) #define repc2(i, s, n) for (int i = (s); i <= (int)(n); i++) #define length(v) ((int)(v).size()) constexpr int inf = 2'000'000'000; constexpr ll linf = 4'000'000'000'000'000'000, M7 = 1'000'000'007, M9 = 998'244'353; #define all(v) begin(v), end(v) #define rall(v) rbegin(v), rend(v) using namespace std; using namespace atcoder; inline ostream& operator<<(ostream& os, lll val) noexcept { string s; bool neg = val < 0; if (val < 0) { val *= -1; } if (val == 0) { s += '0'; } else { while (val > 0) { s += '0' + val % 10; val /= 10; } } reverse(all(s)); if (neg) s = "-" + s; return os << s; } inline istream& operator>>(istream& is, lll& val) noexcept { string s; is >> s; bool neg = false; if (s[0] == '-') { neg = true; s = s.substr(1); } val = 0; for (auto c : s) { val *= 10; val += c - '0'; } if (neg) val *= -1; return is; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int Q; cin >> Q; while (Q--) { lll a, b, k; cin >> a >> b >> k; lll lc = a / gcd(ll(a), ll(b)) * b; auto cmp = [&](lll x) -> bool { lll cnt = x; cnt -= x / a; cnt -= x / b; cnt += x / lc; return cnt >= k; }; auto abs = [](lll x) -> lll { return x < 0 ? -x : x; }; auto bsearch = [&](auto cmp) { lll ok = numeric_limits<lll>::max() / 2, ng = 0; while (abs(ng - ok) > 1) { lll mid = (ng + ok) / 2; if (cmp(mid)) ok = mid; else ng = mid; } return ok; }; cout << bsearch(cmp) << endl; } return 0; }