Pagini recente » Cod sursa (job #2772808) | Cod sursa (job #1644022) | Cod sursa (job #2194728) | Cod sursa (job #2405767) | Cod sursa (job #3236004)
#include <fstream>
using namespace std;
ifstream cin("inversmodular.in");
ofstream cout("inversmodular.out");
typedef long long num;
num euclid(num a, num b, num &x, num &y)
{
x = 1, y = 0;
num x1 = 0, y1 = 1, a1 = a, b1 = b;
while (b1)
{
num q = a1 / b1;
num aux = x1;
x1 = x - q * x1;
x = aux;
aux = y1;
y1 = y - q * y1;
y = aux;
aux = b1;
b1 = a1 - q * b1;
a1 = aux;
}
return a1;
}
int main()
{
size_t n;
cin >> n;
for (size_t i = 0; i < n; i++)
{
num a, b, c, x, y;
cin >> a >> b >> c;
num d = euclid(a, b, x, y);
if (c % d != 0)
{
cout << "0 0\n";
}
else
{
// cout << "gcd: " << d << "\n";
cout << x * (c / d) << " " << y * (c / d) << endl;
}
}
}