Cod sursa(job #2476403)

Utilizator penetavyPene Cosmin-Octavian penetavy Data 18 octombrie 2019 19:46:15
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll i, j, n, m , k;


ll gcd(ll a, ll b) { return __gcd(a, b); }
ll euclid(ll a, ll b, ll &x, ll &y) {
	if (b) { ll d = euclid(b, a % b, y, x);
		return y -= a/b * x, d; }
	return x = 1, y = 0, a;
}

ifstream fin("euclid3.in");
ofstream fout("euclid3.out");

int main() {
//  cin.sync_with_stdio(0);
//  cin.tie(0);
  fin>>n;
  ll a, b, c;
  while (n) {
    fin>>a>>b>>c;

    ll d = gcd(a, b);

//    cout<<d<<" : "<<gcd(a*c/d, b*c/d)<<endl;

    if (c % d != 0) {
      fout<<0<<" "<<0<<"\n";
    }
    else {
      ll x, y;

      a = a * c / d;
      b = b * c / d;

      euclid(a, b, x, y);

      x = x * c / d;
      y = y * c / d;

      fout<<x<<" "<<y<<"\n";
    }

    n--;
  }

  return 0;
}