Pagini recente » Cod sursa (job #126632) | Cod sursa (job #2457131) | Cod sursa (job #1179181) | Cod sursa (job #2027314) | Cod sursa (job #1021942)
#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;
ifstream f("euclid3.in");
ofstream g("euclid3.out");
typedef struct pairs{ int x; int y; } pairs;
int cmmdc(int a, int b){
if (a == 0 || b == 0)
return a + b;
if (a > b) return cmmdc(a % b, b);
else return cmmdc(a, b % a);
}
pairs euclid_extended(int a, int b){
pairs result;
if (b == 1){
result.x = 0;
result.y = -1;
} else if (a == 1){
result.x = 1;
result.y = 0;
} else {
int d, c;
pairs rez;
if(a > b){
d = a / b;
c = a % b;
result = euclid_extended(b, c);
rez.x = - result.y;
rez.y = - (result.x + d * result.y);
} else {
d = b / a;
c = b % a;
result = euclid_extended(a, c);
rez.y = result.y;
rez.x = result.x + d * result.y;
}
return rez;
}
return result;
}
pairs getK(pairs p, int a, int b, int c){
pairs result;
int sign = p.x / abs(p.x);
result.x = p.x;
result.y = p.y;
for(int i = 1; i < abs(c); i++){
result.x+=p.x;
result.y+=p.y;
if (abs(result.x) > abs(b)){
result.x-=sign*b;
result.y-=sign*a;
}
}
if (c < 0){
result.x = - result.x;
result.y = - result.y;
}
return result;
}
void solve(int a, int b, int c){
int cm = cmmdc(abs(a), abs(b));
if (c % cm != 0)
g << "0 0\n";
else{
a = a / cm;
b = b / cm;
c = c / cm;
pairs p = euclid_extended(abs(a), abs(b));
p.x = (a / abs(a)) * p.x;
p.y = (b / abs(b)) * p.y;
pairs k = getK(p, a, b, c);
g << k.x << " " << -k.y << '\n';
}
}
int main() {
int n, a, b, c;
f >> n;
for(int i = 1; i <= n; i++){
f >> a >> b >> c;
solve(a, b, c);
}
f.close();
g.close();
return 0;
}