Pagini recente » Cod sursa (job #2950281) | Cod sursa (job #1069593) | Cod sursa (job #2646079) | Cod sursa (job #195314) | Cod sursa (job #2270289)
#include <fstream>
using namespace std;
pair<int, int> eucl_ext(int a, int b)
{
if (b == 0)
return { 1, 0 };
auto p = eucl_ext(b, a % b);
return {p.second, p.first - a / b * p.second};
}
int main()
{
ifstream f("euclid3.in");
ofstream g("euclid3.out");
int n, x, y, c;
f >> n;
for (int i = 0; i < n; i++)
{
f >> x >> y >> c;
auto p = eucl_ext(x, y);
int d = x * p.first + y * p.second;
if (c % d) g << "0 0\n";
else g << p.first * (c / d) << " " << p.second * (c / d) << "\n";
}
return 0;
}
/*
(a, b) = d |
ak + bl = d | ak + bl = bk' + (a % b)l' | |k = l'
(b, a % b) = d | | => ak + bl = bk' + al' - bl'[a/b] => |l = k' - l'[a/b]
bk' + (a % b)l' = d | |
a = b * [a / b] + a % b => a % b = a - b * [a / b] |
*/