Cod sursa(job #2899869)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 9 mai 2022 12:55:05
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb

/// always:
#include <cstdio>
#include <string>

/// optional:
#include <cassert>
#include <cstring>
#include <iostream>

bool home = 1;
using namespace std;

const string TASKNAME="euclid3";

typedef long long ll;

ll d;

pair<ll, ll> gcd(ll a, ll b) {
  if (b==0) {

    d=a;
    return {1, 0};
  }
  pair<ll, ll> it=gcd(b,a%b);
  return {it.second, it.first-a/b*it.second};
}

signed main() {
#ifdef INFOARENA
  home = 0;
#endif

  if(!home) {
    freopen((TASKNAME + ".in").c_str(), "r", stdin);
    freopen((TASKNAME + ".out").c_str(), "w", stdout);
  }else{
    freopen ("I_am_iron_man", "r", stdin);
  }


  int tests;
  cin>>tests;
  for (int tc=1;tc<=tests;tc++) {
    ll a, b, c;
    cin>>a>>b>>c;
    pair<ll, ll> it=gcd(a,b);
    if(c%d!=0) {
      cout<<"0 0\n";
    } else {
      it.first*=(c/d);
      it.second*=(c/d);
      cout<<it.first<<" "<<it.second<<"\n";
    }
  }
}