Pagini recente » Cod sursa (job #2853131) | Cod sursa (job #1510803) | Cod sursa (job #269185) | Cod sursa (job #674207) | Cod sursa (job #1502864)
#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;
}