Cod sursa(job #2288721)

Utilizator BotzkiBotzki Botzki Data 23 noiembrie 2018 19:44:31
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
vector <int>caturi;
int xf, yf;
int euclid (int a, int b)
{
    int r;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
void euclid_extins(int a, int b)
{
    int r=0, l, x0, y0;
    while(b)
    {
        r=a/b;
        caturi.push_back(r);
        r=a%b;
        a=b;
        b=r;
    }
    x0=1, y0=0;
    l=caturi.size();
    for(int i=l-1;i>=0;i--)
    {
        xf=y0;
        yf=x0-(caturi[i]*y0);
        x0=xf;
        y0=yf;
    }
}
int main()
{
    int b, c, a, d, q;
    fin>>q;
    for(int i=1;i<=q;i++)
    {
       fin>>a>>b>>c;
       d=euclid(a, b);
       if(c%d!=0)
         fout<<"0"<<" "<<"0"<<"\n";
       else
       {
         euclid_extins(a, b);
          fout<<xf*(c/d)<<" "<<yf*(c/d)<<"\n";
         caturi.clear();
       }
    }
    return 0;
}