Pagini recente » Cod sursa (job #2436958) | Cod sursa (job #2076165) | Cod sursa (job #2715375) | Cod sursa (job #50431) | Cod sursa (job #1009538)
#include <fstream>
#include <utility>
using namespace std;
pair<int, int> euclid(int a, int b, int c)
{
//daca b = 0 => a * X = c
if (b == 0)
{
//daca c este divizbil cu a => x = c/a si y = oricat (il vom lua 0)
if (c % a == 0)
return make_pair(c / a, 0);
//daca c nu este divizibiil cu a => x = c/a nu apartine lui Z => nu exista o solutie convenabil
else return make_pair(0, 0);
}
//daca a nu este dibizibil cu b
else if (a % b)
{
//se va apela functia euclid() recursiv, b devenint a iar a%b devine b (de la algoritmul lui euclid)
pair<int, int> r = euclid(b, a % b, c);
//daca s-a ajuns la un caz unde s-a descoperit ca nu exista solutie , transmite mai departe acest lucru
if ( r.first == 0 && r.second == 0)
return r;
//matematic putem deduce ca
//x = y0
//y = x0 - c * y0
//unde x, y sunt numerele din enunt iar x0, y0 sunt numerele de la nivelul de mai jos al stivei
//astfel solutie este construita recursiv in functie de x0, y0 care, la cel mai de jos nivel sunt c / a, 0
return std::make_pair(r.second, r.first - (r.second * (a/b)));
}
//daca b != 0 si a % b == 0 (b == cmmdc (a,b))
else
{
//daca c este divizibil cu b => a * x + b * y = c => |
// vom lua x ca fiind 1 => | => b * y = c - a => y = (c-a) / b) = > y = c/b - a/b;
if (c%b == 0) //deoarece b | a si b | b => b | (a * x + b * y)
{
return make_pair(1, c/b - a/b);
}
//altfel nu exista solutie
else
{
return make_pair(0, 0);
}
}
}
int main()
{
ifstream IN ("euclid3.in");
ofstream OUT ("euclid3.out");
int t; IN >> t;
int c, a, b;
for (int i = 0 ; i < t ; i++)
{
IN >> a >> b >> c;
pair<int, int> r = euclid (a, b, c);
OUT << r.first << " " << r.second << "\n";
}
}