Cod sursa(job #1956789)

Utilizator alex273Groza Alexandru alex273 Data 7 aprilie 2017 01:06:53
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.51 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("euclid3.in"); ofstream out("euclid3.out");

void euclid (int a,int b,int &d,int &x,int &y){
    if (!b) {
    d=a;
    x=1;
    y=0;
    } 
    else {
        euclid(b,a%b,d,x,y);
        int x0=x;
        x=y;
        y=x0-(a/b)*y;
    }
}

int main() {
	int a,b,c,x,y,d;
	int k;
	in>>k;
	while (k--){
	    in>>a>>b>>c;
	    euclid (a,b,d,x,y);
	    if (!(c%d)) out <<x*(c/d)<<" "<<y*(c/d)<<"\n";
	    else out <<"0 0"<<"\n";
	    
	}
	return 0;
}