Cod sursa(job #1502864)

Utilizator jimcarterJim Carter jimcarter Data 15 octombrie 2015 03:03:50
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <cstdio>
#include <stack>
using namespace std;

FILE *f = fopen("euclid3.in","r") , *g = fopen("euclid3.out","w");

int T , a , b , i , c;
stack <int> div;

void gcd( int x , int y , int result )
{
	int d , aux , a , b , a1 , b1 ;

	//make x > y
	if ( x < y ) { aux = x ; x = y ; y = aux ; };

	// d = x MOD y
	d = x % y;
	while ( d )
	{
	    div.push ( x / y );
        x = y;
		y = d;
		d = x % y;
	}
	div.push ( x / y );
    //gcd( x , y ) = d
	d = y;

    if ( c % d )
    {
        fprintf ( g , "0 0\n" );
        return;
    }

	//recover a b s.t. a * x + b * y = d
	a = 1 , b = 0 ;
	while ( !div.empty() )
    {
        aux = div.top();
        a1 = b; b1 = a - b * aux;
        a = a1; b = b1;
        div.pop ();
    }
    a *= c / d , b *= c / d ;
    fprintf ( g , "%d %d\n" , a , b );
}

void read()
{
	fscanf ( f , "%d" , &T );
	for ( i = 1 ; i <= T ; i ++ )
	{
		fscanf ( f , "%d %d %d" , &a , &b , &c );
        gcd ( a , b , c );
	}
}

int main()
{
	read();
	return 0;
}