Cod sursa(job #1682340)

Utilizator AcuasPopescu Nicolae-Aurelian Acuas Data 10 aprilie 2016 10:32:58
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 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;
    if(a<b)
        swap(a,b);
    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;
        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';
    }
    return 0;
}