Cod sursa(job #2649117)

Utilizator Ionut_neuer58Raducu Ioan Stefan Ionut_neuer58 Data 13 septembrie 2020 09:05:56
Problema Algoritmul lui Euclid extins Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.58 kb
#include <iostream>
#include <fstream>

using namespace std;

typedef long long ll;

ifstream in("euclid3.in");
ofstream out("euclid3.out");

ll qry, a, b, c, d, yy, xx;

ll gcd(ll a, ll b, ll &x, ll &y)
{
    if(!b)
    {
        x=y=1;
        return a;
    }
    ll rez, y1, x1;
    rez=gcd(b, a%b, x1, y1);
    x=y1;
    y=x1-a/b*y1;
    return rez;
}

int main()
{
    in>>qry;
    while(qry--)
    {
        in>>a>>b>>c;
        d=gcd(a, b, xx, yy);
        if(c%d) out<<"0 0\n";
        else out<<xx*(c/d)<<' '<<yy*(c/d)<<'\n';
    }
    return 0;
}