Pagini recente » Cod sursa (job #1646165) | Cod sursa (job #2819728) | Cod sursa (job #2565274) | Istoria paginii runda/info_de_performanta/clasament | Cod sursa (job #2479719)
/*
========================= EXPLICARE MATEMATICA ================================
a*x + b*y = c;
Fie d = cmmdc(a,b);
Ca ecuatia sa aiba solutie, c = d sau c = d * k pentru oricare k intreg =>
a*x + b*y = d; (1)
Fie a*x0 + b*y0 = d;
Din euclid =>
Daca b = 0 atunci y0 = 0 si x0 = 1;
b*x0 + (a%b)*y0 = d;
Fie c=a/b =>
a%b = a-b*c =>
b*x0 + (a-b*c)*y0 = d; (2)
1,2 => b*x0 + (a-b*c)*y0 = a*x + b*y;
b*(x0 - c*y0 - y) = a*(x - y0);
=> y = x0 - c*y0;
x = y0
*/
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("euclid3.in");
ofstream out("euclid3.out");
void euclid_extins(int *d, int a, int b, int *x, int *y) {
if (!b) {
*d = a;
*x = 1;
*y = 0;
}
else {
int x0, y0;
euclid_extins(d, b, a % b, &x0, &y0);
*x = y0;
*y = x0 - (a / b) * y0;
}
}
int main()
{
int n, a, b, c, d, x, y;
in >> n;
for (int i = 1; i <= n; i++) {
in >> a >> b >> c;
euclid_extins(&d, a, b, &x, &y);
if (c % d) {
out << "0 0" << '\n';
}
else {
out << x*(c/d) << " " << y*(c/d) << "\n";
}
}
}