Pagini recente » Cod sursa (job #810491) | Cod sursa (job #2821001) | Cod sursa (job #2409336) | Cod sursa (job #2350960) | Cod sursa (job #2772397)
#include <fstream>
#include <list>
#include <utility>
using namespace std;
bool areParticularCases(const long long A, const long long B,
const long long C, ofstream &out) {
if (A == 0LL) {
if (B != 0LL && C % B == 0LL)
out << 1 << ' ' << C / B << '\n';
else
out << "0 0\n";
return true;
} else if (B == 0LL) {
if (A != 0LL && C % A == 0LL)
out << 1 << ' ' << C / A << '\n';
else
out << "0 0\n";
return true;
}
return false;
}
void euclid3(const long long A, const long long B, const long long C,
ofstream &out) {
if (areParticularCases(A, B, C, out))
return;
long long a = A, b = B;
list<pair<long long, long long>> coefStack;
while (b) {
coefStack.push_back({a, b});
long long temp = a;
a = b;
b = temp % b;
}
long long d = a;
if (C % d) {
coefStack.clear();
out << "0 0\n";
return;
}
long long x1 = 1LL, y1 = 0LL;
long long x, y, q;
while (!coefStack.empty()) {
auto &cf = coefStack.back();
coefStack.pop_back();
a = cf.first;
b = cf.second;
q = a / b;
x = y1;
y = x1 - q * y1 * 1LL;
x1 = x;
y1 = y;
}
long long fact = C / d;
x *= fact;
y *= fact;
out << x << ' ' << y << '\n';
}
int main(void) {
ifstream in("euclid3.in");
ofstream out("euclid3.out");
int t, a, b, c;
in >> t;
for (int i = 0; i < t; i++) {
in >> a >> b >> c;
euclid3(a, b, c, out);
}
in.close();
out.close();
return 0;
}