Cod sursa(job #1240983)

Utilizator danny794Dan Danaila danny794 Data 12 octombrie 2014 14:14:02
Problema Algoritmul lui Euclid extins Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <cstdio>
#include <utility>
#include <cmath>

using namespace std;

int gcd(int a, int b)
{
  if(b == 0)
    return a;

  return gcd(b, a % b);
}

void solve(int a, int b, pair<int, int> *sol)
{
  if(b == 0)
  {
    sol->first  = 1;
    sol->second = 1;
    return;
  }

  int r = a % b;
  solve(b, r, sol);
  int aux = sol->second;
  sol->second = sol->first - aux * (a / b);
  sol->first = aux;
}

void read()
{
  freopen("euclid3.in", "r", stdin);
  freopen("euclid3.out", "w", stdout);
  int tests, x, y, z;
  scanf("%d", &tests);
  pair<int, int> p;
  while(tests)
  {
    scanf("%d%d%d", &x, &y, &z);
    int ax = abs(x), ay = abs(y);
    int a = x / ax, b = y / ay, g = gcd(ax, ay);

    if(z % g)
      printf("0 0\n");
    else
    {
      ax = ax / g;
      ay = ay / g;
      z = z / g;

      if(ax > ay)
      {
        solve(ax, ay, &p);
        printf("%d %d\n", a * z * p.first, b * z * p.second);
      }
      else
      {
        solve(ay, ax, &p);
        printf("%d %d\n", a * z * p.second, b * z * p.first);
      }
    }
    tests--;
  }
}

int main() {
  read();
	return 0;
}