Pagini recente » Cod sursa (job #1833441) | Cod sursa (job #1600108) | Cod sursa (job #1452061) | Cod sursa (job #396477) | Cod sursa (job #572985)
Cod sursa(job #572985)
# include <fstream>
using namespace std;
std :: ifstream f ("euclid3.in");
std :: ofstream g ("euclid3.out");
int T, a, b, c, d, s, t;
int euclid_extins (int a, int b, int &s, int &t){
int r, c, s1, s2, t1, t2;
if (!b){
s = 1;
t = 0;
return a;
}
s = 0; t = 1;
s1 = 1; t1 = 0;
s2 = 0; t2 = 1;
r = a % b; c = a / b;
while (r){
s = s1 - s2 * c; s1 = s2; s2 = s;
t = t1 - t2 * c; t1 = t2; t2 = t;
a = b; b = r;
r = a % b; c = a / b;
}
return b;
}
int main (){
for (f >> T; T > 0; --T){
f >> a >> b >> c;
d = euclid_extins (a, b, s, t);
if (c % d) g << "0 0\n";
else g << s * (c / d) << ' ' << t * (c / d) << '\n';
}
g.close ();
return 0;
}