Cod sursa(job #2292335)

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

using namespace std;

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

    return a;
  }

  long long 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 )
  {
    long long a, b, c;

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

    long long d, x, y;

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

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

    q--;
  }
  return 0;
}