Cod sursa(job #563068)

Utilizator biroBiro Alexandru biro Data 24 martie 2011 13:03:16
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <algorithm>

using namespace std ;

int n ;
long long A,B,C ;

long long euclid(long long a, long long b,long long& x , long long& y) {
  if (b==0) {
    x=1 ;
    y=0 ;
    return a ; 
  }
  long long 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 ("%lld%lld%lld" , &A , &B , &C ); 
    long long d , x , y ; 
    d=euclid(A,B,x,y) ;
    if (C%d)
      printf ("0 0\n") ;
    else 
      printf ("%lld %lld\n" , x*C/d , y*C/d) ;
  }
   
  return 0;  
}