Pagini recente » Cod sursa (job #250391) | Cod sursa (job #1157522) | Cod sursa (job #3290710) | Cod sursa (job #1971578) | Cod sursa (job #449208)
Cod sursa(job #449208)
#include<fstream>
using namespace std;
long x[10000],y[10000],r[10000];
long cmmdc(long a,long b)
{
if(a%b==0)return b;
return cmmdc(b,a%b);
}
int main()
{
long a,b,c,e,d,u,w,c1,c2,c3,i,n,j,sa,sb;
ifstream f("euclid3.in");
ofstream g("euclid3.out");
f>>n;
for(j=1;j<=n;j++)
{f>>a>>b>>c;
sa=sb=1;
if(a<0){sa=-1;a=-a;}
if(b<0){sb=-1;b=-b;}
d=cmmdc(a,b);
if(c%d!=0)g<<"0 0\n";
else
{if(a%b==0){u=0;w=1;}
else
{e=a%b;
if(b%e==0){u=1;w=-a/b;}
else{r[1]=a%b;c1=a/b;
x[1]=1;y[1]=-c1;
r[2]=b%r[1];
c2=b/r[1];
x[2]=-c2;
y[2]=1+c1*c2;
i=2;
do{i++;
c3=r[i-2]/r[i-1];
r[i]=r[i-2]%r[i-1];
x[i]=x[i-2]-c3*x[i-1];
y[i]=y[i-2]-c3*y[i-1];
}while(r[i]!=0);
u=x[i-1]; w=y[i-1];
}
}
u=u*(c/d); w=w*(c/d);
u=u*sa;
w=w*sb;
g<<u<<' '<<w<<'\n';
}
}
}