Cod sursa(job #1266257)

Utilizator xtreme77Patrick Sava xtreme77 Data 18 noiembrie 2014 15:43:59
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
/*
 * Code by Spiromanul
 */


#include <fstream>

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

using namespace std;


ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;

inline int extended_gcd ( int a , int b , int &xxx , int &yyy )
{
    if ( not b ){
        xxx = 1 ;
        yyy = 0 ;
        return a ;
    }
    int x0 , y0 ;
    int D = extended_gcd ( b , a % b , x0 , y0 ) ;
    xxx = y0 ;
    int aux = a / b ;
    yyy = x0 - aux * y0 ;
    return D ;
}

int main (              )
{
    int t ;
    fin >> t ;
    for ( ; t ; -- t )
    {
        int a , b , c ;
        fin >> a >> b >> c ;
        int x , y , d ;
        d = extended_gcd ( a , b , x , y ) ;
        if ( c % d )
            fout << "0 0\n" ;
        else fout << ( c / d ) * x << ' ' << ( c / d ) * y << '\n' ;
    }
    return 0;
}