Cod sursa(job #2331688)

Utilizator Gl0WCula Stefan Gl0W Data 29 ianuarie 2019 19:58:12
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>

using namespace std;

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

int t, aa, bb, cc, x, y, rr;

int euclid_extins(int a, int b, int &x, int &y ){
	if(b == 0){
		x = 1;
		y = 0;
		return a;
	}
    else{
        int x0, y0;
        int r = euclid_extins(b, a % b, x0, y0);
        x = y0;
        y = x0 - y0 * (a / b);
        return r;
	}
}

int main()
{
    fin>>t;
    for(int i = 1; i <= t; i++){
        fin>>aa>>bb>>cc;
        rr = euclid_extins(aa, bb, x, y);
        if(cc % rr){
            fout<<"0 0\n";
        }
        else{
            fout<<x * (cc / rr)<<" "<<y * (cc / rr)<<"\n";
        }
    }
    return 0;
}