Cod sursa(job #1477324)

Utilizator CalinSpiridonSpiridon Calin CalinSpiridon Data 25 august 2015 21:51:15
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>

using namespace std;

ifstream fin("euclid3.in");
ofstream fout("euclid3.out");

int t, p, q, r, x, y;

int cmmdc(int e, int f){
    int g=0;
    while(f){
        g=e%f;
        e=f;
        f=g;
    }
    return e;
}
void euclid(int a, int b, int d, int &x, int &y){
    if(b==0){
        x=1;
        y=0;
    }
    else{
        int x0,y0;
        euclid(b, a%b, d, x0, y0);
        x=y0;
        y=x0-(a/b)*y0;
    }
}

int main(){
    fin>>t;
    while(t){
        --t;
        fin>>p>>q>>r;
        int gcd=cmmdc(p,q);
        if(r%gcd) fout<<0<<' '<<0<<'\n';
        else{
            euclid(p, q, gcd, x, y);
            int sol_1=r/gcd*x;
            int sol_2=r/gcd*y;
            fout<<sol_1<<' '<<sol_2<<'\n';
        }
    }



    return 0;
}