Pagini recente » Cod sursa (job #2829643) | Cod sursa (job #374928) | Cod sursa (job #2298946) | Cod sursa (job #1047979) | Cod sursa (job #2487864)
#include <fstream>
std::ifstream fin("euclid3.in");
std::ofstream fout("euclid3.out");
long long max(long long a, long long b) {
if (a > b)
return a;
else return b;
}
void euclid_extins(long long *x, long long *y, long long a, long long b, long long c)
{
if (b == 0)
{
*x = 1;
*y = 0;
}
else {
long long x0, y0;
euclid_extins(&x0, &y0, b, a%b, c);
*x = y0;
*y = x0 - (a / b)* y0;
}
}
long long cmmdc(int a, int b)
{
if (a*b != 0)
if (a < b)
return cmmdc(a, b%a);
else
return cmmdc(a%b, b);
else return max(a, b);
}
int main()
{
short T;
fin >> T;
long long a, b, c;
long long x = 0, y = 0;
for (int i = 0; i < T; i++) {
fin >> a >> b >> c;
long long d = cmmdc(a, b);
if (c%d != 0)
fout << 0 << " " << 0 << std::endl;
else
{
euclid_extins(&x, &y, a, b, d);
fout << x*c/d << " " << y*c/d << std::endl;
}
}
}