Cod sursa(job #1682347)

Utilizator AcuasPopescu Nicolae-Aurelian Acuas Data 10 aprilie 2016 10:36:32
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
using namespace std;
ifstream cin("euclid3.in");
ofstream cout("euclid3.out");
int ExtendEuclid(int a,int b,int &lastX,int &lastY){
    int x=0,y=1;
    lastX=1,lastY=0;
    int q,r;
    int tX,tY;
    while(b){
        q=a/b;
        r=a%b; a=b; b=r;
        tX=x; x=lastX-q*x; lastX=tX;
        tY=y; y=lastY-q*y; lastY=tY;
    }
    return a;
}
int main(){
    int t,a,b,d,i;
    int x,y;
    cin>>t;
    for(i=1;i<=t;i++){
        cin>>a>>b>>d;
        if(a>b){
            int x,y;
            int r=ExtendEuclid(a,b,x,y);
            if(d%r)
                cout<<0<<' '<<0<<'\n';
            else
                cout<<x*(d/r)<<' '<<y*(d/r)<<'\n';
        }
        else{
            int x,y;
            int r=ExtendEuclid(b,a,y,x);
            if(d%r)
                cout<<0<<' '<<0<<'\n';
            else
                cout<<x*(d/r)<<' '<<y*(d/r)<<'\n';
        }
    }
    return 0;
}