Cod sursa(job #2539665)

Utilizator claudiumsimaSima Mihai Claudiu claudiumsima Data 6 februarie 2020 09:48:37
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 0.95 kb
/**
 *Se dau T ecuatii de forma a * x + b * y = c, cu coeficientii a, b si c.
 *Pentru fiecare dintre aceste ecuatii se cere aflarea unei perechi de
 *numere intregi x y care sa satisfaca ecuatia, in cazul in care o astfel de pereche exista.
 */

#include <iostream>
#include <fstream>

using namespace std;

void euclid(int a, int b, int *d, int *x, int *y)
{
    if(!b)
    {
        *d = a;
        *x = 1;
        *y = 0;
    }
    else
    {
        int x0, y0;
        euclid(b, a%b, d, &x0, &y0);
        *x = y0;
        *y = x0 - y0*(a/b);
    }

}

int main()
{
    ifstream f("euclid3.in");
    ofstream g("euclid3.out");

    int t; f >> t;
    for(int i = 0; i < t; i++)
    {
        int a, b, c, x, y, d;
        f >> a >> b >> c;
        euclid(a, b, &d, &x, &y);


        if(c%d)
            g << "0 0\n";
        else{
            g << x*(c/d) << " " << y*(c/d) << endl;
        }

    }

    return 0;
}