Cod sursa(job #2590357)

Utilizator ioana0211Ioana Popa ioana0211 Data 27 martie 2020 19:40:04
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
using namespace std;
ifstream fin ("euclid3.in");
ofstream fout ("euclid3.out");
int t;
struct elem
{
    int div;
    int x0;
    int y0;
};
elem euclid_extins (int a, int b)
{
    if(b==0)
    {
        elem ultim;
        ultim.div=a; ultim.x0=1; ultim.y0=0;
        return ultim;
    }
    elem d=euclid_extins(b, a%b); //obtinem si x0, y0
    //calculam x, y
    elem nou;
    nou.x0=d.y0;
    nou.y0=d.x0-(a/b)*d.y0;
    nou.div=d.div;
    return nou;
}
int main()
{
    fin>>t;
    int a, b, c;
    for(int i=1; i<=t; i++)
    {
        fin>>a>>b>>c;
        elem rez=euclid_extins(a, b);
        if(c%rez.div)
            fout<<"0 0\n";
        else
            fout<<rez.x0 * (c/rez.div)<<" "<<rez.y0 * (c/rez.div)<<"\n";
    }
    return 0;
}