Pagini recente » Cod sursa (job #2050359) | Cod sursa (job #1524618) | Cod sursa (job #2032214) | Cod sursa (job #1710574) | Cod sursa (job #2240876)
//
// EuclidExtended.cpp
// InfoArena
//
// Created by Tim Palade on 9/14/18.
// Copyright © 2018 Tim Palade. All rights reserved.
//
#include <stdio.h>
using namespace std;
void euclidExtended(int a, int b, int *x, int *y, int *d) {
if (b == 0) {
*d = a;
*x = 1;
*y = 0;
}
else {
int x0, y0;
euclidExtended(b, a%b, &x0, &y0, d);
*x = y0;
*y = x0 - (a/b) * y0;
}
}
int main(int argc, const char * argv[]) {
// insert code here...
int T;
freopen("euclid3.in", "r", stdin);
freopen("euclid3.out", "w", stdout);
scanf("%d", &T);
for (; T; --T)
{
int a, b, c, x, y, d;
scanf("%d %d %d", &a, &b, &c);
euclidExtended(a, b, &x, &y, &d);
//printf("x = %d | y = %d | gcd = %d\n", x, y, d);
//assert(x * a + y * b == d);
if (c % d != 0) { //no solutions
//write 0 to the file
printf("%d %d\n", 0, 0);
}
else { //has solutions
// a * alpha + b * beta = c
// alpha = (c/d) * x
// beta = (c/d) * y
int m = c / d;
int alpha = m * x;
int beta = m * y;
printf("%d %d\n", alpha, beta);
//assert(alpha * a + beta * b == c);
}
}
return 0;
}