Cod sursa(job #2455402)
Utilizator | Alexandra Cordunasu alexa_cordunasu | Data | 11 septembrie 2019 18:05:01 |
---|---|---|---|
Problema | Algoritmul lui Euclid extins | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.83 kb |
#include <fstream>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
void cmmdc(int a,int b,int &d,int &x,int &y)
{
int r,r0,r1,x0,x1,y0,y1,q;
r0=a;
r1=b;
x0=1;
y0=0;
x1=0;
while(r1!=0)
{
q=r0/r;
r=r0-r1*q;
r0=r1;
r1=r;
x=x0-x1*q;
x0=x1;
x1=x;
y=y0-y1*q;
y0=y1;
y1=y;
}
d=r0;
x=x0;
y=y0;
}
int main()
{
int a,b,c,T,x,y,d;
fin>>T;
for(int i=1;i<=T;i++)
{
fin>>a>>b>>c;
cmmdc(a,b,d,x,y);
if(c%d!=0)
fout<<"0 0"<<endl;
else
{
x=x*(c/d);
y=y*(c/d);
fout<<x<<" "<<y<<endl;
}
}
fin.close();
fout.close();
return 0;
}