Cod sursa(job #1007378)

Utilizator lucky1992Ion Ion lucky1992 Data 8 octombrie 2013 20:45:43
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

int main(){

	freopen("euclid3.in", "r", stdin );
	freopen("euclid3.out", "w", stdout );
	
	int T, a,b,c;
	
	scanf("%d", &T );
	
	for( int i = 0; i < T; i++ ){
	
		int x = 0, y = 1,lastx = 1,lasty = 0,rest,q,aux1,aux2;
		scanf("%d%d%d", &a, &b, &c );
		
		
		while( b != 0 ){
			rest = a % b;
			q = a/b;
			
			a = b;
			b = rest;
			
			aux1 = x;
			aux2 = y;
			
			x = lastx - q*x;
			y = lasty - q*y;
			
			lastx = aux1;
			lasty = aux2;
		}
		
			cerr<<"gcd este: "<< a <<endl;
			if( c%a == 0 )
				printf("%d %d\n", lastx*(c/a), lasty*(c/a) );
			else
				printf("0 0\n");
		}
		
		return 0;
		
}