Cod sursa(job #3123092)

Utilizator CondoracheAlexandruCondorache Alexandru CondoracheAlexandru Data 21 aprilie 2023 20:27:20
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.59 kb
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int maxn=1e5+5;
 int solve(int a,int b,int &x,int &y){
 	if(b==0){
 		x=1;
 		y=0;
 		return a;
	}
	else{
		int x0,y0,d;
		d=solve(b,a%b,x0,y0);
		x=y0;
		y=x0-(a/b)*y0;
		return d;
	}
 }
 int main(){
 	ifstream cin("euclid3.in");
 	ofstream cout("euclid3.out");
	int t;
	cin >> t;
	while(t--){
		int a,b,c,x,y,d;
		cin >> a >> b >> c;
		d=solve(a,b,x,y);
		if(c%d!=0){
			cout << "0 0" << endl;
		}
		else{
			cout << x*(c/d) << " " << y*(c/d) << endl;
		}
	}
 	return 0;
}