Cod sursa(job #3339396)

Utilizator GliggyGligor Andrei Gliggy Data 7 februarie 2026 19:03:18
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.52 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
long long t,a,b,c,i,x,y,d;

long long gcd(long long a,long long b){return b==0?a:gcd(b,a%b);}
void rec(long long a,long long b){
	if(b==0){x=1;y=0;return;}
	rec(b,a%b);
	long long xx=y;
	y=x-y*(a/b);
	x=xx;
}

int main(){
	fin>>t;
	for(i=1;i<=t;i++){
		fin>>a>>b>>c;
		d=gcd(a,b);
		if(c%d!=0) fout<<"0 0\n";
		else{
			rec(a,b);
			x*=c/d;
			y*=c/d;
			fout<<x<<" "<<y<<"\n";
		}
	}
	return 0;
}