結果
問題 |
No.2183 LCA on Rational Tree
|
ユーザー |
![]() |
提出日時 | 2024-12-29 20:46:43 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,429 ms / 2,000 ms |
コード長 | 2,589 bytes |
コンパイル時間 | 2,124 ms |
コンパイル使用メモリ | 149,196 KB |
実行使用メモリ | 5,760 KB |
最終ジャッジ日時 | 2024-12-29 20:46:49 |
合計ジャッジ時間 | 5,526 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 6 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <cassert> #include <cmath> #include <numeric> // for gcd #include <unordered_map> using namespace std; // キャッシュ機能を実現するためのunordered_mapを使用 unordered_map<long long, vector<long long>> divisor_cache; // 整数Nのすべての約数を求める関数 vector<long long> Divisors(long long N) { if (divisor_cache.count(N)) return divisor_cache[N]; vector<long long> divisors; for (long long i = 1; i * i <= N; ++i) { if (N % i == 0) { divisors.push_back(i); if (i != N / i) divisors.push_back(N / i); } } sort(divisors.begin(), divisors.end()); return divisor_cache[N] = divisors; } // 木構造を構築する関数 vector<tuple<long long, long long, long long>> tree(long long p, long long q) { vector<tuple<long long, long long, long long>> retu; vector<long long> D = Divisors(q - p); const long long M = 1e18; while (q - p >= 2) { long long mi = M; for (size_t i = 1; i < D.size(); ++i) { if ((q - p) % D[i] == 0) { mi = min(mi, (-p) % D[i] + D[i]); // 値の正規化 } } long long pp = p + mi; long long qq = q + mi; long long g = gcd(pp, qq); retu.emplace_back(q - p, p, pp); p = pp / g; q = qq / g; } retu.emplace_back(1, p, M); return retu; } int main() { int Q; cin >> Q; while (Q--) { long long a, b, c, d; cin >> a >> b >> c >> d; auto tree0 = tree(a, b); auto tree1 = tree(c, d); assert(tree0.size() <= 30); assert(tree1.size() <= 30); sort(tree0.begin(), tree0.end()); sort(tree1.begin(), tree1.end()); long long D = 0, A = 0; while (!tree0.empty() && !tree1.empty()) { if (get<0>(tree0.back()) < get<0>(tree1.back())) { tree1.pop_back(); } else if (get<0>(tree0.back()) > get<0>(tree1.back())) { tree0.pop_back(); } else { auto [d0, a0, b0] = tree0.back(); auto [d1, a1, b1] = tree1.back(); tree0.pop_back(); tree1.pop_back(); long long a = max(a0, a1); long long b = min(b0, b1); if (a <= b) { D = d0; A = a; break; } } } cout << A << " " << A + D << endl; } return 0; }