Cod sursa(job #2398079)

Utilizator LazarRazvanLazar Razvan LazarRazvan Data 5 aprilie 2019 01:23:54
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
//============================================================================
// Name        : Eulcid.cpp
// Author      : Razvan
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <fstream>

using namespace std;

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

int a, b, x, y, gcd, c, nr;

int Euclid(int a, int b, int &x, int &y)
{
    if (a == 0)
    {
        x = 0;
        y = 1;
        return b;
    }

    int x1, y1; // To store results of recursive call
    int gcd = Euclid(b%a, a, x1, y1);

    // Update x and y using results of recursive
    // call
    x = y1 - (b/a) * x1;
    y = x1;

    return gcd;
}

int main()
{
   fin >> nr;
   for (int i=1; i<=nr; i++)
   {
	   fin >> a >> b >> c;
	   if(a < b)
	   {
		   int aux = a;
		   a = b;
		   b = aux;
	   }

	   gcd = Euclid(a, b, x, y);
	   //cout << "GCD: " << gcd << "\nx = " << x << "\ny = " << y << endl;
	   if (1.0*c/gcd == c/gcd)
	   {
		   fout << c/gcd*x << " " << c/gcd*y << '\n';
	   }
	   else
		   fout << "0 0\n";
   }
   return 0;
}