Cod sursa(job #2386890)

Utilizator davidisimo040Asandoaiei David davidisimo040 Data 23 martie 2019 20:31:17
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
long long a,b,c,x,y; long long xa=1,xb=0,ya=0,yb=1,cc,za,zb;
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
int t,i,ok;
        fin>>t;
        for(i=1;i<=t;i++)
        {

    fin>>a>>b>>c;
    ok=0;
long long d=gcd(a,b);
//fout<<c<<endl;
    if(c%d!=0) fout<<0<<' '<<0<<'\n';
    else
    {   if(a<b) {ok=1;swap(a,b);}
       xa=1;xb=0;ya=0;yb=1;
        cc=a%b;
        while(cc!=0){
        za=xa-(a/b)*ya;
        zb=xb-(a/b)*yb;
        xa=ya;xb=yb;ya=za;yb=zb;
        a=b;b=cc;
cc=a%b;
        }
        if(ok==0)fout<<za*c/d<<' '<<zb*c/d<<'\n';
        else if(ok==1) fout<<zb*c/d<<' '<<za*c/d<<'\n';

    }



    }
    return 0;
}