Cod sursa(job #2661956)

Utilizator vlad_butnaruVlad Butnaru vlad_butnaru Data 23 octombrie 2020 08:08:42
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
using namespace std;
ifstream in ("euclid3.in");
ofstream out ("euclid3.out");
int euclid (int a, int b, int d, int &x, int &y)
{
    if (b==0)
    {
        x = 1;
        y = 0;
        d = a;
    }
    else
    {
        int x0, y0;
        euclid (b,a%b,d,x0,y0);
        x = y0;
        y = x0 - (a/b) * y0;
    }

}
int cmmdc (int x, int y)
{
    while (y)
    {
        int rest = x % y;
        x = y;
        y = rest;
    }
    return x;
}
int main ()
{
    int t;
    in>>t;
    while (t--)
    {
        int a,b,c;
        in>>a>>b>>c;
        int x = cmmdc (a,b);
        if (c%x!=0)
            out<<"0 0\n";
        else
        {
            int rez1, rez2;
            euclid (a,b,x,rez1,rez2);
            out<<rez1*(c/x)<<' '<<rez2*(c/x)<<'\n';
        }
    }
    return 0;

}