Cod sursa(job #2944457)

Utilizator matei0000Neacsu Matei matei0000 Data 22 noiembrie 2022 16:27:29
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>

using namespace std;

ifstream cin("euclid3.in");
ofstream cout("euclid3.out");

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

int GCD(int a, int b)
{
    int c;
    while(b)
    {
        c=a%b;
        a=b;
        b=c;
    }
    return a;
}

int main()
{
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        int a,b,c,d,x,y;
        cin>>a>>b>>c;
        if(c%GCD(a,b)!=0)
            cout<<"0 0\n";
        else
        {
            euclid (a,b,d,x,y);
            cout<<c/d*x<<" "<<c/d*y<<'\n';
        }
    }
    return 0;
}