2020牛客多校第三场 F-Fraction Construction Problem

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const int N = 2e6 + 5;
bool isnp[N];
int pfactor[N];
vector<int> primes;
 
void init() {
    isnp[0] = isnp[1] = 1;
    pfactor[1] = 1;
    for (int i = 2; i < N; ++i) {
        if (!isnp[i]) {
            primes.emplace_back(i);
            pfactor[i] = i;
        }
        for (int x : primes) {
            if (1LL * x * i >= N) break;
            isnp[x * i] = 1;
            pfactor[x * i] = x;
            if (i % x == 0) break;
        }
    }
}
 
ll ex_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    ll gcd = ex_gcd(b, a % b, y, x);
    y -= (a / b) * x;
    return gcd;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    init();
    cin >> t;
    while(t--) {
        ll a, b;
        cin >> a >> b;
 
        ll gcd = __gcd(a, b);
 
        if (gcd > 1) {
            ll c = (a + b) / gcd, d = b / gcd, e = 1, f = 1;
            cout << c << ' ' << d << ' ' << e << ' ' << f << '\n';
            continue;
        }
 
        ll k = pfactor[b], d = 1, f = b;
        while (k != 1 && f % k == 0) {
            d *= k;
            f /= k;
        }
 
        if (f == 1) {
            cout << "-1 -1 -1 -1\n";
            continue;
        }
 
        ll c, e;
        ex_gcd(d, f, e, c);
        e = -e;
        while (c <= 0 || e <= 0) {
            c += d;
            e += f;
        }
        c *= a, e *= a;
 
        cout << c << ' ' << d << ' ' << e << ' ' << f << '\n';
    }
    return 0;
}

本文地址：https://blog.csdn.net/qq_43624815/article/details/107568324