Cod sursa(job #2801117)

Utilizator qubitrubbitQubit Rubbit qubitrubbit Data 14 noiembrie 2021 23:15:47
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");

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

bool solve(int a, int b, int c, int &x0, int &y0)
{
    int g = gcd_ex(abs(a), abs(b), x0, y0);
    if (c % g != 0)
    {
        return false;
    }
    x0 *= c / g;
    y0 *= c / g;
    if (a < 0)
    {
        x0 *= -1;
    }
    if (b < 0)
    {
        y0 *= -1;
    }
    return true;
}

int a, b, c, t;
int main()
{
    fin >> t;
    while (t-- > 0)
    {
        fin >> a >> b >> c;
        int x, y;
        if (!solve(a, b, c, x, y))
        {
            fout << "0 0\n";
        }
        else
        {
            fout << x << " " << y << "\n";
        }
    }
    return 0;
}