Cod sursa(job #1061865)

Utilizator DuxarFII-Stefan-Negrus Duxar Data 20 decembrie 2013 13:22:20
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<utility>
#include<cstdio>
#include<cmath>

#define LL long long 

using namespace std ;

LL A, B, D ;
pair <pair <LL, LL>, LL> C ;
pair <pair <LL, LL>, LL> gcd (LL A, pair<LL, LL> pA, LL B, pair <LL, LL> pB) ;

int main() {
	LL cat ;
	int N, i ;
	freopen("euclid3.in", "r", stdin) ;  
	freopen("euclid3.out", "w", stdout) ;
	scanf("%d", &N) ;
	for (i = 1; i <= N; ++i) {
		scanf("%lld %lld %lld", &A, &B, &D) ;
		C = gcd (A, make_pair(1, 0), B, make_pair(0, 1)) ;
		
		if ((long long)abs(D) % C.second == 0) {
			cat = abs(D) / C.second ;
			if (D < 0) cat *= -1 ;
			//printf("%lld\n", cat) ;
			printf("%lld %lld\n", cat * C.first.first, cat * C.first.second) ;
		} 
		else {
			printf("0 0\n") ;
		}
	}
	return 0 ;
}

pair <pair <LL, LL>, LL> gcd (LL A, pair<LL, LL> pA, LL B, pair <LL, LL> pB) {
	LL cat, rest ;
	pair <LL, LL> C ;
	cat = A / B ;
	rest = A % B ;
	if (rest == 0) return make_pair(pB, B) ;
	C.first = pA.first - cat * pB.first ;
	C.second = pA.second - cat * pB.second ;
	return gcd(B, pB, rest, C) ;
}