Mai intai trebuie sa te autentifici.
Cod sursa(job #1218699)
Utilizator | Data | 12 august 2014 12:35:05 | |
---|---|---|---|
Problema | Algoritmul lui Euclid extins | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.71 kb |
#include <cstdio>
using namespace std;
long long A,B,C;
void euclid(long long a,long long b,long long &d, long long &x,long long &y)
{
if(!b)
{
d = a;
x = 1;
y = 0;
return;
}
long long x1,y1;
euclid(b,a%b,d,x1,y1);
x = y1;
y = x1 -(a/b)*y1;
}
int main()
{
freopen("euclid3.in","r",stdin);
freopen("euclid3.out","w",stdout);
int T;
scanf("%d", &T);
for(int i = 1; i <= T; ++i){
scanf("%lld%lld%lld", &A, &B, &C);
long long x,y,d;
euclid(A,B,d,x,y);
if( C % d != 0)
printf("0 0\n");
else
printf("%lld %lld\n", x*C/d, y*C/d);
}
return 0;
}