Cod sursa(job #1241017)

Utilizator danny794Dan Danaila danny794 Data 12 octombrie 2014 14:40:08
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 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 = 0;
    return a;
  }

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

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