結果
問題 | No.2066 Simple Math ! |
ユーザー |
👑 ![]() |
提出日時 | 2022-09-02 22:11:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 218 ms / 2,000 ms |
コード長 | 2,353 bytes |
コンパイル時間 | 1,713 ms |
コンパイル使用メモリ | 193,616 KB |
最終ジャッジ日時 | 2025-02-07 01:20:46 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 31 |
ソースコード
#define _USE_MATH_DEFINES#include <bits/stdc++.h>using namespace std;#define FOR(i,m,n) for(int i=(m);i<(n);++i)#define REP(i,n) FOR(i,0,n)#define ALL(v) (v).begin(),(v).end()using ll = long long;constexpr int INF = 0x3f3f3f3f;constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;constexpr double EPS = 1e-8;constexpr int MOD = 998244353;// constexpr int MOD = 1000000007;constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1};constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1};constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1};template <typename T, typename U>inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; }template <typename T, typename U>inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; }struct IOSetup {IOSetup() {std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);std::cout << fixed << setprecision(20);}} iosetup;long long floor_sum(long long a, long long b, long long m, long long n) {long long res = 0;if (a < 0) {long long nxt_a = a % m;if (nxt_a < 0) nxt_a += m;res -= n * (n - 1) / 2 * ((nxt_a - a) / m);a = nxt_a;}if (b < 0) {long long nxt_b = b % m;if (nxt_b < 0) nxt_b += m;res -= n * ((nxt_b - b) / m);b = nxt_b;}while (true) {if (a >= m) {res += n * (n - 1) / 2 * (a / m);a %= m;}if (b >= m) {res += n * (b / m);b %= m;}const long long y_max = a * n + b;if (y_max < m) break;b = y_max % m;n = y_max / m;std::swap(a, m);}return res;}void solve() {int p, q, k; cin >> p >> q >> k;const int g = gcd(p, q);p /= g; q /= g;if (p > q) swap(p, q);const ll less_than_pq = floor_sum(-p, 1LL * p * q - 1, q, q) + q - 1;if (less_than_pq < k) {cout << (1LL * p * q + (k - less_than_pq - 1)) * g << '\n';return;}ll lb = p - 1, ub = 1LL * p * q - 1;while (ub - lb > 1) {const ll mid = (lb + ub) / 2;(floor_sum(-p, mid, q, mid / p + 1) + mid / p < k ? lb : ub) = mid;}cout << ub * g << '\n';}int main() {int t; cin >> t;while (t--) solve();return 0;// FOR(p, 1, 100) FOR(q, 1, 100) {// if (gcd(p, q) > 1) continue;// set<int> s;// REP(x, q) REP(y, p) {// if (p * x + q * y < p * q) assert(s.emplace(p * x + q * y).second);// }// }}