Cod sursa(job #2208067)

Utilizator Laura_CorneiLaura Maria Cornei Laura_Cornei Data 28 mai 2018 10:21:09
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
using namespace std;
fstream f1("euclid3.in", ios::in);
fstream f2("euclid3.out", ios::out);
int nrt, a, b, c, d;
void euclid_extins(int a, int b, int &x, int &y)
{
    if(b==0)
    {
        d=a;x=1;y=0;
    }
    else
    {
        euclid_extins(b, a%b, x, y);
        int aux=y;
        y=x-y*(a/b);
        x=aux;
    }
}
int main()
{
     int x, y;
     f1>>nrt;
     while(nrt--)
     {
         f1>>a>>b>>c;
         euclid_extins(a, b, x, y); ///x,y solutie a ecuatiei a*x+b*y=c (c!=0), sau 0 0 daca ecuatia nu are solutie
         ///d=(a, b), pt ca ec sa aiba solutie d divide c (id bezout, daca d=(a, b) rezulta exista u, v intregi a.i. d=u*x+v*y)
         ///x, y initiale = solutie pentru ecuatia a*x+b*y=d
         if(c%d==0) f2<<x*(c/d)<<' '<<y*(c/d)<<"\n";
         else f2<<0<<' '<<0<<"\n";
     }
     return 0;
}