Cod sursa(job #1240968)

Utilizator danny794Dan Danaila danny794 Data 12 octombrie 2014 13:52:06
Problema Algoritmul lui Euclid extins Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <cstdio>
#include <utility>
#include <cmath>

using namespace std;

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

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

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);
    long long a = x / abs(x), b = y / abs(y);
    if(x > y)
    {
      int gcd = solve(abs(x), abs(y), &p);
      if(z % gcd != 0)
        printf("0 0\n");
      else
        printf("%lld %lld\n", a * (z / gcd) * p.first, b * (z / gcd) * p.second);
    }
    else
    {
      int gcd = solve(abs(y), abs(x), &p);
      if(z % gcd != 0)
        printf("0 0\n");
      else
        printf("%lld %lld\n", a * (z / gcd) * p.second, b * (z / gcd) * p.first);
    }
    tests--;
  }
}

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