結果

問題 No.2183 LCA on Rational Tree
ユーザー vwxyz
提出日時 2024-06-02 04:31:15
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,752 bytes
コンパイル時間 2,744 ms
コンパイル使用メモリ 132,720 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2024-12-22 21:48:10
合計ジャッジ時間 11,878 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

const long long M=1LL<<60;

long long gcd(long long a,long long b){
    if(a>b){
        return gcd(b,a);
    }
    if(a==0){
        return b;
    }
    return gcd(b%a,a);
}
vector<long long> Divisors(long long N) {
    vector<long long> divisors;
    long long i;
    for (i = 1; i * i < N; ++i) {
        if (N % i == 0) {
            divisors.push_back(i);
        }
    }
    if (i * i == N) {
        divisors.push_back(i);
    }
    for (--i; i > 0; --i) {
        if (N % i == 0) {
            divisors.push_back(N / i);
        }
    }
    return divisors;
}

// Recursive function to generate tree nodes
vector<tuple<long long, long long, long long>> f(long long p, long long q, const vector<long long>& D) {
    if (q - p == 1) {
        return { make_tuple(1, p, M) };
    }
    vector<tuple<long long, long long, long long>> lst;
    vector<long long> mods;
    for (size_t i = 1; i < D.size(); ++i) {
        long long d = D[i];
        if ((q - p) % d == 0) {
            mods.push_back((d+(-p) % d)%d);
        }
    }
    long long mi = *min_element(mods.begin(), mods.end());
    long long pp = p + mi;
    long long qq = q + mi;
    long long g = gcd(pp, qq);
    lst.push_back(make_tuple(q - p, p, pp));
    vector<tuple<long long, long long, long long>> sub_lst = f(pp / g, qq / g, D);
    lst.insert(lst.end(), sub_lst.begin(), sub_lst.end());
    return lst;
}

// Function to generate the tree
vector<tuple<long long, long long, long long>> tree(long long p, long long q) {
    vector<long long> D = Divisors(q - p);
    return f(p, q, D);
}

int main() {
    int Q;
    cin >> Q;
    for (int q = 0; q < Q; ++q) {
        long long a, b, c, d;
        cin >> a >> b >> c >> d;
        vector<tuple<long long, long long, long long>> tree0 = tree(a, b);
        vector<tuple<long long, long long, long long>> tree1 = tree(c, d);

        unordered_map<long long, vector<pair<long long, long long>>> dct;
        for (const auto& [d, a, b] : tree0) {
            dct[d].emplace_back(a, b);
        }
        for (const auto& [d, a, b] : tree1) {
            dct[d].emplace_back(a, b);
        }
        vector<pair<long long, long long>> lst;
        for (const auto& [d, v] : dct) {
            if (v.size() == 2) {
                auto [a0, b0] = v[0];
                auto [a1, b1] = v[1];
                long long a = max(a0, a1);
                long long b = min(b0, b1);
                if (a <= b) {
                    lst.emplace_back(d, a);
                }
            }
        }

        auto [y, x] = *min_element(lst.begin(), lst.end());
        cout << x << " " << x + y << endl;
    }

    return 0;
}
0