Cod sursa(job #2504295)

Utilizator eutu33eu tu el ea eutu33 Data 4 decembrie 2019 19:41:06
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <fstream>

using namespace std;

long long gcdExtended(long long a, long long b, long long &x, long long &y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    long long xn, yn;
    long long gcd = gcdExtended(b % a, a, xn, yn);
    x = yn - (b / a) * xn;
    y = xn;
    return gcd;
}

int main()
{
    ifstream in ("euclid3.in");
    ofstream out ("euclid3.out");

    long long a,b,c,x,y;
    long long t;
    in>>t;
    for(int i=0;i<t;i++)
    {
        in>>a>>b>>c;
        int d = gcdExtended(a, b, x, y);
        if (c % d)
            out<<"0 0"<<"\n";
        else
            out<<x*(c/d)<<" "<<y*(c/d)<<"\n";
    }
    return 0;
}