Cod sursa(job #2176659)

Utilizator VasilcoiuAnaVasilcoiu Ana VasilcoiuAna Data 17 martie 2018 21:36:59
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
using namespace std;

void euclid_extins(int a,int b,int c,int &x,int &y)
{
    ///presupunem ca apelam aceasta functzie DOAR daca shtim sigur ca avem solutzie, altfel da eronat
    if(b==0)
    {
        x=c/a;
        y=0;
    }
    else
    {
        int q=a/b;///calculez citurile in variabila locala q pt. ca se le am
        ///shi atunci cind revenim
        euclid_extins(b,a%b,c,x,y);
        ///pe baza lui x shi y ii calculez pe cei noi shi apoi ii atribui TOT pt. x,y
        int xnou=y;
        int ynou=x-q*y;
        x=xnou;
        y=ynou;
    }
}

int cmmdc(int a,int b)
{
    int r;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}

int main()
{
    ifstream fin("euclid3.in");
    ofstream fout("euclid3.out");
    int x,y,a,b,c,d,t;
    fin>>t;
    for(int i=1; i<=t; i++)
    {
        fin>>a>>b>>c;
        d=cmmdc(a,b);
        if(c%d)fout<<"0 0\n";
        else
        {
            a/=d;b/=d;c/=d;///simplificam ecuatzia cu d
            euclid_extins(a,b,c,x,y);
            fout<<x<<" "<<y<<"\n";
        }
    }
    return 0;
}