Cod sursa(job #2841128)

Utilizator Cosmin2004_InfoMoldoveanu Cosmin Cosmin2004_Info Data 29 ianuarie 2022 12:26:19
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>

using namespace std;
#ifdef INFOARENA
#define cin fin
#define cout fout
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
#endif // INFOARENA
using ll = long long;
ll extgcd(ll a, ll b, ll* x, ll* y) {
    if(a == 0) {
        *x = 0;
        *y = 1;
        return b;
    }
    ll x1, y1;
    ll gcd = extgcd(b % a, a, &x1, &y1);
    *x = y1 - (b / a) * x1;
    *y = x1;
    return gcd;
}

int main()
{
    int t;
    cin >> t;
    while(t--) {
        ll a, b, c, x, y;
        cin >> a >> b >> c;
        ll gcd = extgcd(a, b, &x, &y);
        if(abs(c) % abs(gcd) == 0) {
            int coeff = c / gcd;
            cout << coeff * x << " " << coeff * y << "\n";
        } else cout << "0 0\n";
    }
    return 0;
}