Pagini recente » Cod sursa (job #3253876) | Cod sursa (job #2145966) | Cod sursa (job #2284269) | Cod sursa (job #1590828) | Cod sursa (job #841302)
Cod sursa(job #841302)
//cerinta: a * x + b * y = cmmdc(a, b)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
void euclid(int a, int b, int c, int *x, int *y)
{
if (a == c)
{
*x = 1;
*y = 0;
return;
}
else if (b == c)
{
*x = 0;
*y = 1;
return;
}
vector<int> cat;
int r, n;
while (b != 0)
{
r = a % b;
cat.push_back(a / b);
a = b;
b = r;
}
if (c % a != 0)
{
*x = 0; *y = 0;
return;
}
n = cat.size();
n--;
int xx = 1, yy = -cat[n-1];
for (int i = n-2; i >=0; i--)
{
int t = yy;
yy = xx - yy * cat[i];
xx = t;
}
int d = c / a;
*x = xx * d;
*y = yy * d;
}
int main()
{
int a, b, c, m;
ifstream f("euclid3.in");
ofstream g("euclid3.out");
f>>m;
int x, y;
for (int i = 0; i<m; i++)
{
f>>a>>b>>c;
euclid(a, b, c, &x, &y);
g<<x<<" "<<y<<"\n";
}
f.close(); g.close();
return 0;
}