Cod sursa(job #2651220)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 21 septembrie 2020 19:24:30
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

ll d;

pair<ll, ll> gg(ll a, ll b)
{
    if (b == 0)
    {
        d = a;
        return {1, 0};
    }
    else
    {
        pair<ll, ll> it = gg(b, a % b);
        return {it.second, it.first - (a / b) * it.second};
    }
}

pair<ll, ll> cf(ll a, ll b, ll c)
{
    pair<ll, ll> it = gg(a, b);
    if (c % d)
    {
        return {0, 0};
    }
    it.first *= (c / d);
    it.second *= (c / d);
    return it;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    freopen ("euclid3.in", "r", stdin);
    freopen ("euclid3.out", "w", stdout);

    int t;
    cin >> t;
    while (t--)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        pair<ll, ll> it = cf(a, b, c);
        cout << it.first << " " << it.second << "\n";
    }
}