Pagini recente » Cod sursa (job #2697060) | Cod sursa (job #3251373) | Cod sursa (job #1550162) | Cod sursa (job #297582) | Cod sursa (job #2105888)
#include <fstream>
using namespace std;
ifstream f("euclid3.in");
ofstream g("euclid3.out");
/*
consideram b = 0 => a * 1 + b * 0 = a(cmmdc)
( initial x = 1 si y = 0 )
cunoastem urmatoarele relatii matematice:
b * x0 + (a % b) * y0 = d (relatia 1)
a * x + b * y = d (relatia 2)
pentru a determina o pereche (x, y) cu proprietatea ceruta, notam a/b cu c => a % b = a - b * c
relatiile 1 si 2 => b * x0 + (a - b * c) * y0 = a * x + b * y <=> b * (x0 - c * y0 - y) = a * (x - y0)
daca egalam fiecare paranteza cu 0, se observa o solutie:
x0 - c * y0 - y = 0 => y = x0 - c * y0
x - y0 = 0 => x = y0
*/
inline int euclid(int a, int b, int &x, int &y)
{
if (b == 0) {
x = 1;
y = 0;
return a;
}
else {
int d, x0, y0;
d = euclid(b, a%b, x0, y0);
x = y0;
y = x0 - (a / b)*y0;
return d;
}
}
int main()
{
int t;
for (f >> t; t; t--) {
int a, b, c, d, x, y;
f >> a >> b >> c;
d = euclid(a, b, x, y);
if (c % d) g << "0 0" << '\n';
else g << x*(c / d) << ' ' << y*(c / d) << '\n';
}
f.close();
g.close();
return 0;
}