Cod sursa(job #1515199)

Utilizator c0rn1Goran Cornel c0rn1 Data 1 noiembrie 2015 11:49:43
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <cstdio>
#include <algorithm>

using namespace std;

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

int main()
{
   int n;
   long long int a, b, c, d, x, y;
   freopen("euclid3.in", "r", stdin);
   freopen("euclid3.out", "w", stdout);
   scanf("%d\n", &n);
   for (int i = 1; i <= n; ++i){
      scanf("%lld %lld %lld\n", &a, &b, &c);
      d = cmmdc(a, b, x, y);
      if (c%d != 0){
         printf("0 0\n");
         continue;
      }
      printf("%lld %lld\n", x*c/d, y*c/d);
   }

   return 0;
}