Pagini recente » Cod sursa (job #1603109) | Cod sursa (job #560202) | Cod sursa (job #389277) | Cod sursa (job #318001) | Cod sursa (job #2909452)
//Problema Algoritmul lui Euclid extins - Rezolvare C++: 100p -> infoarena.ro
//Stud. Cristian CRIȘAN - AC, CTI-RO, ANUL I
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
int euclid_exstins(int &x, int &y, int a, int b) //algoritmul lui Euclid extins
{
if(b == 0)
{
x = 1;
y = 0;
return a;
}
else
{
int x1, y1;
int t = euclid_exstins(x1, y1, b, a % b); //facem inca un pas al algoritmului
x = y1;
y = x1 - y1 * (a / b);
return t;
}
}
void solve(int n)
{
int a, b, c, x = 0, y = 0, t;
while(n --)
{
fin >> a >> b >> c;
t = euclid_exstins(x, y, a, b);
if(c % t) //daca c nu este divizibil cu t nu exista solutie
fout << "0 0\n";
else
fout << x * (c / t) << ' ' << y * (c / t) << '\n';
}
}
int main()
{
int n;
fin >> n;
solve(n);
return 0;
}