Cod sursa(job #2692177)

Utilizator ARobertAntohi Robert ARobert Data 1 ianuarie 2021 14:21:17
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <bits/stdc++.h>
#define int int64_t
#define cin fin
#define cout fout

using namespace std;

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

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

bool find_any_solution(int a, int b, int c, int &x0, int &y0, int &g)
{
    g = gcd(abs(a), abs(b), x0, y0);
    if (c % g)
    {
        return false;
    }

    x0 *= c / g;
    y0 *= c / g;
    if (a < 0)
        x0 = -x0;
    if (b < 0)
        y0 = -y0;
    return true;
}

int32_t main()
{
    int t, a, b, c, x, y, d;
    cin >> t;
    for (int i = 1; i <= t; i++)
    {
        cin >> a >> b >> c;
        int ok = 0;
        if (a > b)
            swap(a, b), ok = 1;
        if (a == 0 && b == 0)
        {
            cout << "0 0\n";
        }
        else if (a==0)
        {
            int x=0,y=0;
            if (c%b==0) y=c/b;
            if (ok) swap(x,y);
            cout<<x<<" "<<y<<'\n';
        }
        else if (b==0)
        {
            int x=0,y=0;
            if (c%a==0) y=c/a;
            if (ok) swap(x,y);
            cout<<x<<" "<<y<<'\n';
        }
        else if (find_any_solution(a, b, c, x, y, d))
        {
            int bd = b / d;
            int ad = a / d;
            int aux = y / ad;
            y = y - aux * ad;
            x = x + aux * bd;
            if (ok)
                swap(x, y);
            cout << x << " " << y << '\n';
        }
        else
        {
            cout << "0 0\n";
        }
    }
    return 0;
}