Cod sursa(job #2292327)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 29 noiembrie 2018 13:36:32
Problema Algoritmul lui Euclid extins Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.61 kb
#include <cstdio>

using namespace std;

int gcd( int a, int b, int &x, int &y )
{
  if( b==0 )
  {
    x=1;
    y=0;

    return a;
  }

  int d, x0, y0;

  d=gcd(b,a%b,x0,y0);

  x=y0;
  y=x0-y0*(a/b);

  return d;
}

int main()
{
  freopen( "euclid3.in", "r", stdin );
  freopen( "euclid3.out", "w", stdout );

  int q;

  scanf( "%d", &q );

  while( q )
  {
    int a, b, c;

    scanf( "%d%d%d", &a, &b, &c );

    int d, x, y;

    d=gcd(a,b,x,y);

    if( c%d )
      printf( "0 0\n" );
    else
      printf( "%d %d\n", x*c/d, y*c/d );

    q--;
  }
  return 0;
}