Cod sursa(job #2724880)

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

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


int exgcd(int a, int b){
	int c, q;

	int 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;
			int x1 = s1*n;
			int x2 = t1*n;
			cout << n<<'\n';
			fout << s1*n << " "<< t1*n<<'\n';
		}
	}
	
	return 0;
}