欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-24 18:34:23
#include using namespace std;using ll = long long; const int N = 2e6 + 5;bool isnp[N];int pfactor[N];vector primes; void init() { isnp[0] = isnp[1] = 1; pfactor[1] = 1; for (int i = 2; i < N; ++i) {....

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

相关标签: 基础算法 算法