Cod sursa(job #2605122)

Utilizator KlinashkaDiacicov Calin Marian Klinashka Data 24 aprilie 2020 14:36:22
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>

using namespace std;

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

int euclidextins(int a, int b, long long &x, long long &y)
{
    long long x0=1, x1=0, y0=0, y1=1, aux, q;
    int r0=a, r1=b;
    while(r0%r1!=0)
    {
        q=r0/r1;
        aux=x0-q*x1;
        x0=x1;
        x1=aux;
        aux=y0-q*y1;
        y0=y1;
        y1=aux;
        q=r0%r1;
        r0=r1;
        r1=q;
    }
    x=x1;
    y=y1;
    return r1;
}

short T, neg1, neg2;
int a, b, c, r;
long long x, y;

int main()
{
    fin>>T;
    for(short i=0;i<T;i++)
    {
        fin>>a>>b>>c;
        neg1=1;
        neg2=1;
        if(a<0)
        {
            a=-a;
            neg1=-1;
        }
        if(b<0)
        {
            b=-b;
            neg2=-1;
        }
        r=euclidextins(a, b, x, y);
        if(c%r==0)
        {
            c=c/r;
            x=x*neg1*c;
            y=y*neg2*c;
            fout<<x<<' '<<y<<'\n';
        }
        else
            fout<<0<<' '<<0<<'\n';
    }
    return 0;
}