Cod sursa(job #2549196)

Utilizator tudorcioc5Cioc Tudor tudorcioc5 Data 17 februarie 2020 13:49:05
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
using namespace std;

// Function for extended Euclidean Algorithm
long long gcdExtended(long long a, long long b, long long &x, long long &y)
{
	// Base Case
	if (b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}

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

	x = y1;
	y = x1 - (a/b) * y1;

	return gcd;
}

ifstream fin;
ofstream fout;

long long aux;

int main()
{
	long long x, y, a , b, c, n;

	fin.open("euclid3.in");
	fout.open("euclid3.out");
	fin>>n;

    for (long long i=1; i<=n; i++){

        x = 0 , y = 0;
        fin>>a>>b>>c;


        long long g = gcdExtended(a, b, x, y);

        if (c % g == 0){
            aux = c/g;
            x *= aux;
            y *= aux;
            fout<<x<<" "<<y<<"\n";
        } else{
            fout<<0<<" "<<0<<"\n";
        }
    }
    fin.close();
    fout.close();

	return 0;
}