Cod sursa(job #2724884)

Utilizator vladvaculinVlad V vladvaculin Data 18 martie 2021 00:37:42
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.61 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");

int a,b,c,s1,s2,t1,t2;


int exgcd(int a, int b){
	int c, q, x;
	while(b){
		c = a % b;
		q = a / b;
		x = s1 - q*s2;
		s1 = s2;
		s2 = x;
		
		x = t1 - q*t2;
		t1=t2;
		t2=x;
		a = b;
		b = c;
	}
	
	return a;
}
int main() {
	int nr;
	fin>>nr;
	
	for (int i = 0; i<nr; i++){
		fin >> a>> b >> c;
		s1 = 1;
		s2 = 0;
		t1 = 0;
		t2 = 1;
		int x = exgcd(a, b);
		if(c%x){
			fout << "0 0\n";
		} else {
			int n = c/x;
			fout << s1*n << " "<< t1*n<<'\n';
		}
	}
	
	return 0;
}