Pagini recente » Cod sursa (job #2601992) | Cod sursa (job #1315141) | Cod sursa (job #1443526) | Cod sursa (job #2036003) | Cod sursa (job #2801118)
#include <fstream>
using namespace std;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
int gcd_ex(int a, int b, int &x, int &y)
{
if (a == 0)
{
x = 0;
y = 1;
return b;
}
int x1, y1;
int d = gcd_ex(b % a, a, x1, y1);
x = y1 - (b / a) * x1;
y = x1;
return d;
}
bool solve(int a, int b, int c, int &x0, int &y0)
{
int g = gcd_ex(abs(a), abs(b), x0, y0);
if (c % g != 0)
{
return false;
}
x0 *= c / g;
y0 *= c / g;
if (a < 0)
{
x0 *= -1;
}
if (b < 0)
{
y0 *= -1;
}
return true;
}
int a, b, c = 1;
int main()
{
fin >> a >> b;
int x, y;
if (!solve(a, b, c, x, y))
{
fout << "0 0\n";
}
else
{
fout << x;
}
return 0;
}