Cod sursa(job #563064)

Utilizator biroBiro Alexandru biro Data 24 martie 2011 12:58:08
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <algorithm>

using namespace std ;

int n ;
int A,B,C ;

int euclid(int a, int b,int& x , int& y) {
  if (b==0) {
    x=1 ;
    y=0 ;
    return a ; 
  }
  int x0 , y0 , d;
  d=euclid(b,a%b,x0,y0) ;
  x=y0 ;
  y=x0-(a/b)*y0;
  return d ;
}

int main() {
  freopen ("euclid3.in","r",stdin) ;
  freopen ("euclid3.out","w",stdout) ; 
  
  scanf ("%d" , &n) ;
  
  for (int i=1 ; i<=n ; ++i) {
    scanf ("%d%d%d" , &A , &B , &C ); 
    int d , x , y ; 
    d=euclid(A,B,x,y) ;
    if (C%d)
      printf ("0 0\n") ;
    else 
      printf ("%d %d\n" , x*C/d , y*C/d) ;
  }
   
  return 0;  
}