Cod sursa(job #1144687)
Utilizator | Data | 17 martie 2014 14:11:05 | |
---|---|---|---|
Problema | Algoritmul lui Euclid extins | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.66 kb |
#include <cstdio>
using namespace std;
FILE*f=fopen("euclid3.in", "r");
FILE*g=fopen("euclid3.out", "w");
int n, t, x, y, d, D, a, b, c;
int cmmdc(int a, int b, int &x, int &y){
if(b==0)
{
x=1;
y=0;
return a;
}
int x0, y0, d;
d=cmmdc(b, a%b, x0, y0);
x=y0;
y=x0-y0*(a/b);
return d;
}
int main(){
fscanf(f, "%d", &t);
for(;t;t--)
{
fscanf(f, "%d %d %d", &a, &b, &c);
d=cmmdc(a, b, x, y);
D=c/d;
x*=D;
y*=D;
if(c%d)
fprintf(g, "0 0\n");
else
fprintf(g, "%d %d\n", x, y);
}
return 0;
}