Cod sursa(job #2408215)

Utilizator flaviu_2001Craciun Ioan-Flaviu flaviu_2001 Data 17 aprilie 2019 18:46:19
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;

const string file = "euclid3";
const ll INF = 9223372036854775807ll;
const int inf = 2147483647;

int test;

void gcd(int &x, int &y, int a, int b)
{
    if(b == 0){
        x = 1;
        y = 0;
    }else{
        gcd(x, y, b, a%b);
        int aux = x;
        x = y;
        y = aux-(a/b)*y;
    }
}

int main()
{
    ifstream fin (file+".in");
    ofstream fout (file+".out");
    fin >> test;
    for (int t = 1; t <= test; ++t){
        int a, b, c, d;
        fin >> a >> b >> d;
        c = __gcd(a, b);
        if(d%c != 0){
            fout << "0 0\n";
            continue;
        }
        a /= c;
        b /= c;
        int x, y;
        gcd(x, y, a, b);
        x *= d/c;
        y *= d/c;
        fout << x << " " << y << "\n";
    }
    return 0;
}