Cod sursa(job #1232208)

Utilizator florinpocolPocol Florin florinpocol Data 22 septembrie 2014 13:31:48
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
/*
  Cerinta: Se dau T ecuatii de forma a * x + b * y = c, cu coeficientii a, b si c.
  Pentru fiecare dintre aceste ecuatii se cere aflarea unei perechi de numere intregi x y
  care sa satisfaca ecuatia, in cazul in care o astfel de pereche exista.

  Indicatii de rezolvare:
  Ecuatiile pot fi rezolvate cu ajutorul algoritmului lui Euclid extins, prezentat in acest articol
  de pe infoarena. Astfel se poate determina perechea (x y) care satisface relatia a * x + b * y = d,
  unde d este cmmmdc(a, b). In cazul in care c nu se divide cu d ecuatia nu poate fi rezolvata in multimea
  numerelor intregi, in caz contrar se inmulteste intreaga ecuatie cu c / d.
*/
#include <fstream>
#include <iostream>
using namespace std;

int t,a,b,c,d,x,y;  //c<>0 daca nu la impartire ar fi dat eroare

void euclid_extins(int a, int b, int &d, int &x, int &y)
{
   if (b==0)
      {
        d = a;
        x = 1;
        y = 0;
    }
    else
    {
        int x0, y0;
        euclid_extins(b, a % b, d, x0, y0);
        x = y0;
        y = x0 - (a / b) * y0;
    }

}

void citire()
{
    int i;
    ifstream f("euclid3.in");
    ofstream g("euclid3.out");

    f>>t;
    for (i=1; i<=t; i++)
    {
        f>>a>>b>>c;
        euclid_extins(a,b,d,x,y);
        if(c % d == 0)
            g<<x * (c / d)<<" "<<y * (c / d)<<"\n";
        else
            g<<"0 0\n";
    }

    f.close();
    g.close();
}

int main()
{
    citire();
    return 0;
}