Cod sursa(job #1657755)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 20 martie 2016 19:34:33
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<fstream>
using namespace std;
ifstream  fin("euclid3.in");
ofstream fout("euclid3.out");

int a,b,c,x,y,d,x1,y1;
int T;

int euclid_extins(int a, int b, int &x, int &y){
    int d,x0,y0;
    if(b==0){
        ///cmmdc este a
        x=1;y=0;return a;
    }
    d=euclid_extins(b,a%b,x0,y0);
    x=y0;
    ///deoarece avem a*x+b*y=d=b*x0+(a%b)*y0
    ///y=(b*x0+(a%b)*y0-a*x)/b = (b*x0+(a%b)*y0-a*y0)/b = x0 - y0*(a-(a%b))/b = x0 - y0*(a/b)
    y=x0-y0*(a/b);
    return d;
}

int main(){
    fin>>T;
    while(T){
        fin>>a>>b>>c;
        d=euclid_extins(a,b,x,y);
        if(c%d!=0){
            fout<<"0 0\n";
        }
        else{
            ///a*x+b*y=d, inmultim cu c/d si avem a*(c/d)*x+b*(c/d)*y=c
            x1=(c/d)*x; y1=(c/d)*y;
            fout<<x1<<" "<<y1<<"\n";
        }
        T--;
    }
    fout.close();
    fin.close();
    return 0;
}