Pagini recente » Cod sursa (job #2482882) | Cod sursa (job #766889) | Cod sursa (job #1892053) | Cod sursa (job #2743535) | Cod sursa (job #1114515)
//Sa se determine x,y numere intregi astfel incat ele sa respecte ecuatia:
//a*x+b*y=c , unde a,b,c sunt numere intregi
//Ideea: Se foloseste algoritmul lui Euclid extins
//Plecam de la cazul de baza cand b=0 si cmmdc=a si atunci a*1+b*0=a, deci initial x=1, y=0 cand b=0;
//Incercam apoi sa calculam x,y la pasul curent in functie de x0 si y0 calculate la pasul anterior
// b*x0 + (a%b)*y0 = d
// a*x + b*y = d
//
// Notam c = [a/b] => a%b = a-c*b;
// Egaland ecuatiile obtinem x = y0 si y = x0 - c*y0
#include <iostream>
#include <fstream>
#include <cstdlib>
const char InFile[] = "euclid3.in";
const char OutFile[] = "euclid3.out";
int euclid_extins(int a, int b, int& x, int& y)
{
if( b == 0 ){
x = 1;
y = 0;
return a;
}
int x0, y0, d;
d = euclid_extins(b, a%b, x0, y0);
y = x0 - (a/b)*y0;
x = y0;
return d;
}
void readAndSolve(std::istream& in, std::ostream& out)
{
int n, a, b, c, d, x, y;
in >> n;
for( int i=0 ; i<n ; i++ ){
in >> a >> b >> c;
d = euclid_extins(a, b, x, y);
if( c % d ){
out << 0 << ' ' << 0 << '\n';
} else {
x = x * (c/d);
y = y * (c/d);
out << x << ' ' << y << '\n';
}
}
}
int main(void)
{
std::ifstream in(InFile);
std::ofstream out(OutFile);
readAndSolve(in, out);
return 0;
}