結果
問題 | No.2066 Simple Math ! |
ユーザー | 👑 Nachia |
提出日時 | 2022-09-02 23:39:20 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 193 ms / 2,000 ms |
コード長 | 2,722 bytes |
コンパイル時間 | 595 ms |
コンパイル使用メモリ | 78,320 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-16 06:35:01 |
合計ジャッジ時間 | 5,291 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 7 ms
6,816 KB |
testcase_02 | AC | 17 ms
6,820 KB |
testcase_03 | AC | 6 ms
6,816 KB |
testcase_04 | AC | 178 ms
6,816 KB |
testcase_05 | AC | 184 ms
6,820 KB |
testcase_06 | AC | 182 ms
6,820 KB |
testcase_07 | AC | 178 ms
6,820 KB |
testcase_08 | AC | 177 ms
6,820 KB |
testcase_09 | AC | 186 ms
6,820 KB |
testcase_10 | AC | 189 ms
6,820 KB |
testcase_11 | AC | 193 ms
6,820 KB |
testcase_12 | AC | 183 ms
6,816 KB |
testcase_13 | AC | 186 ms
6,820 KB |
testcase_14 | AC | 174 ms
6,816 KB |
testcase_15 | AC | 174 ms
6,816 KB |
testcase_16 | AC | 177 ms
6,816 KB |
testcase_17 | AC | 178 ms
6,820 KB |
testcase_18 | AC | 184 ms
6,816 KB |
testcase_19 | AC | 59 ms
6,820 KB |
testcase_20 | AC | 57 ms
6,816 KB |
testcase_21 | AC | 60 ms
6,816 KB |
testcase_22 | AC | 57 ms
6,816 KB |
testcase_23 | AC | 58 ms
6,820 KB |
testcase_24 | AC | 94 ms
6,820 KB |
testcase_25 | AC | 94 ms
6,820 KB |
testcase_26 | AC | 94 ms
6,816 KB |
testcase_27 | AC | 93 ms
6,816 KB |
testcase_28 | AC | 91 ms
6,816 KB |
testcase_29 | AC | 32 ms
6,816 KB |
testcase_30 | AC | 6 ms
6,820 KB |
testcase_31 | AC | 10 ms
6,816 KB |
ソースコード
#line 1 "Main.cpp" #include <iostream> #include <string> #include <vector> #include <algorithm> #line 2 "nachia\\math\\floor-sum.hpp" #include <cassert> #include <utility> namespace nachia{ // a : any value // mod != 0 std::pair<long long, unsigned long long> SafeDiv(long long a, unsigned long long mod){ using u64 = unsigned long long; if(a >= 0) return std::make_pair(0, (u64)a); if(mod >= (u64)1 << 62) return std::make_pair(-1, (u64)a + mod); long long q = a / mod; long long m = a % (long long)mod; if(m){ q--; m += mod; } return std::make_pair(q, m); } unsigned long long nC2Uint64(unsigned long long n){ return (n%2) ? ((n-1)/2*n) : (n/2*(n-1)); } // n : any // 1 <= m // a : any // b : any // n * a%m + b%m < 2**64 unsigned long long FloorSumU64Unsigned( unsigned long long n, unsigned long long m, unsigned long long a, unsigned long long b ){ using u64 = unsigned long long; assert(1 <= m); u64 ans = 0; while(n){ if(a >= m){ ans += a / m * nC2Uint64(n); a %= m; } if(b >= m){ ans += b / m * n; b %= m; } u64 y_max = a * n + b; if (y_max < m) return ans; n = y_max / m; b = y_max % m; y_max = a; a = m; m = y_max; } return ans; } // n : any // 1 <= m // a : any // b : any // (n+1) * m < 2**64 unsigned long long FloorSumU64Signed( unsigned long long n, unsigned long long m, long long a, long long b ){ using u64 = unsigned long long; auto ua = SafeDiv(a, m); auto ub = SafeDiv(b, m); u64 ans = FloorSumU64Unsigned(n, m, ua.second, ub.second); ans += ua.first / m * nC2Uint64(n); ans += ub.first / m * n; return ans; } } // namespace nachia #line 8 "Main.cpp" using namespace std; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; #define rep(i,n) for(int i=0; i<(int)(n); i++) u64 GCD(u64 a, u64 b){ if(b == 0) return a; return GCD(b, a%b); } int main(){ int T; cin >> T; rep(i,T){ u64 P,Q,K; cin >> P >> Q >> K; u64 g = GCD(P,Q); P /= g; Q /= g; if(P > Q) swap(P,Q); u64 l = 0, r = P*Q; auto f = [&](u64 N) -> u64 { return nachia::FloorSumU64Unsigned(N/P+1, Q, P, N%P) + (N/P); }; while(l + 1 < r){ u64 N = (l+r)/2; if(f(N) < K) l = N; else r = N; } if(r == P*Q) r = P*Q + (K-f(P*Q)) + 1; cout << r*g << '\n'; } return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } ios_do_not_sync_instance;