Pagini recente » Cod sursa (job #1885660) | Cod sursa (job #695895) | Cod sursa (job #2397752) | Istoria paginii runda/simulareinfo_oji_7_9/clasament | Cod sursa (job #1069122)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
namespace euclid3
{
void gcd(int A, int B, int* r, int* q, int& x, int& y)
{
if (A == 0 && B == 0) x = y = 0;
else if (A == 0) { x = 0; y = (B > 0 ? 1 : -1); }
else if (B == 0) { x = (A > 0 ? 1 : -1); y = 0; }
else {
r[1] = A; //r[1] = max(A, B);
r[2] = B; //r[2] = min(A, B);
int i = 1;
while (r[i + 1])
{
i++;
q[i + 1] = r[i - 1] / r[i];
r[i + 1] = r[i - 1] % r[i];
}
//at this point r[i+1] = 0 and r[i] is the last non-zero remainder, the gcd of A and B
//build x and y such that r1 * x + r2 * y = ri
x = 1, y = -q[i];
int s = 1;
for (int n = i; n > 3; n--)
{
int x_ = x;
x = y;
y = (x_ - y*q[n - 1]);
}
}
}
}
//int e_002_euclid3()
int main()
{
using namespace euclid3;
string in_file = "euclid3.in";
string out_file = "euclid3.out";
int T;
int r[1000], q[1000];
ifstream ifs(in_file);
ofstream ofs(out_file);
ifs >> T;
for (int i = 1; i <= T; i++)
{
int A, B, C;
ifs >> A >> B >> C;
int x, y;
gcd(A, B, r, q, x, y);
int gcd_ab = A*x + B*y;
if (gcd_ab != 0 && C % gcd_ab == 0) {
int k = C / gcd_ab;
ofs << x * k << " " << y * k << '\n';
}
else {
ofs << 0 << " " << 0 << '\n';
}
}
ofs.close();
ifs.close();
return 0;
}