Cod sursa(job #2430068)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 12 iunie 2019 16:51:36
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
#define lll long long
#define pii pair<int,int>
#define pll pair<lll,lll>
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define sz(a) (int)(a).size()
#define inf (1<<30)
#define aaa system("pause");
#define dbg(x) cerr<<(#x)<<' '<<(x)<<'\n',aaa

using namespace std;

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

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

void gcda ( int a, int b, pii &xy )
{
  if ( b == 0 ) { xy = {1, 0}; return; }
  gcda (b, a%b, xy);
  xy = {xy.se, xy.fi - (a/b)*xy.se};
}

int main ()
{
  int t; fin >> t;
  int i, j, z, a, b, c, d;
  pii xy;
  while (t--)
  {
    fin >> a >> b >> d;
    gcda (a, b, xy);
    c = gcd (a, b);
    if ( d % c == 0 ) fout << xy.fi * (d/c) << ' ' << xy.se * (d/c) << '\n';
    else fout << "0 0\n";
  }
  fin.close ();
  fout.close ();
  return 0;
}