Cod sursa(job #3265215)

Utilizator Andrei_DumyDumitrescu Andrei-George Andrei_Dumy Data 28 decembrie 2024 09:00:18
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.56 kb
#include<fstream>

using namespace std;

ifstream cin("euclid3.in");
ofstream cout("euclid3.out");


int gcd(int a, int b, int& x, int& y) {
  if (b == 0) 
  {
    x = 1;
    y = 0;
    return a;
  }
  int x1, y1, d;
  d=gcd(b, a % b, x1, y1);
  x = y1;
  y = x1 - (a / b)* y1;
  return d;
}

int main()
{
  ios::sync_with_stdio(false);
  
  int n, a, b, res;
  cin>>n;

  for(int i=0; i<n; i++)
  {
    cin>>a>>b>>res;
    
    int x, y;
    int d=gcd(a, b, x, y);

    if(res%d!=0)
      cout<<"0 0\n";
    else
      cout<<x*(res/d)<<" "<<y*(res/d)<<"\n";
  }

  return 0;
}