Pagini recente » Cod sursa (job #1186650) | Cod sursa (job #2220384) | Cod sursa (job #2223320) | Cod sursa (job #1854495) | Cod sursa (job #1744524)
#include <algorithm>
#include <string>
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <cassert>
#include <ctime>
using namespace std;
#ifdef INFOARENA
#define TEST 0
#else
#define TEST 1
#endif
struct Input {
int a, b, c;
};
class ExtendedEuclid {
public:
void Solve(long long a, long long b, long long &d,
long long &x, long long &y) {
if (b == 0) {
x = 1;
y = 0;
d = a;
return;
} else {
long long x0, y0;
Solve(b, a%b, d, x0, y0);
x = y0;
y = x0 - (a/b) * y0;
}
}
};
int main() {
vector<Input> input;
if (TEST) {
input.push_back({24,15,147});
input.push_back({24,16,104});
input.push_back({2,4,5});
} else {
freopen("euclid3.in","r",stdin);
freopen("euclid3.out","w",stdout);
}
ExtendedEuclid *instance = new ExtendedEuclid();
for (const Input& in : input) {
long long x, y, d;
instance->Solve(in.a, in.b, d, x, y);
if (in.c % d == 0) {
printf("%lld %lld\n", (in.c / d) * x, (in.c / d) * y);
} else {
printf("0 0\n");
}
}
return 0;
}