Cod sursa(job #1612012)

Utilizator xtreme77Patrick Sava xtreme77 Data 24 februarie 2016 17:32:56
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
/**
 * Code by Patrick Sava
 * "Spiru Haret" National College of Bucharest
 **/

# include "fstream"
# include "cstring"
# include "vector"
# include "queue"
# include "bitset"
# include "algorithm"
# include "map"
# include "set"
# include "unordered_map"
# include "deque"
# include "string"
# include "iomanip"
# include "cmath"
# include "stack"
# include "cassert"

const char IN [ ] =  "euclid3.in" ;
const char OUT [ ] = "euclid3.out" ;

using namespace std ;

# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( register int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( register int a = b ; a >= c ; -- a )

ifstream cin ( IN ) ;
ofstream cout ( OUT ) ;

inline void extended_euclid ( int a , int b , int c , int &aa , int &bb )
{
    if ( b == 0 ) {
        aa = 1 ;
        bb = 0 ;
        return ;
    }
    int yy , zz ;
    extended_euclid( b , a % b , c , yy , zz ) ;
    aa = zz ;
    bb = yy - a / b * zz ;
}

int main ( void )
{
    int t ;
    cin >> t ;
    while ( t -- )
    {
        int a , b , c ;
        cin >> a >> b >> c ;
        if ( c % __gcd ( a , b ) ) {
            cout << 0 << ' ' << 0 << '\n' ;
            continue ;
        }
        else {
            int aaa , bbb ;
            int aux = c / __gcd ( a , b ) ;
            extended_euclid( a , b , __gcd ( a , b ) , aaa , bbb ) ;
            cout << 1LL * aaa * aux << ' ' << 1LL * bbb * aux << '\n' ;
        }
    }
    return 0;
}