Cod sursa(job #1114289)

Utilizator toncuvasileToncu Vasile toncuvasile Data 21 februarie 2014 14:27:28
Problema Algoritmul lui Euclid extins Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
//Infoarena. Arhiva Educationala. Algoritmul lui Euclid Extins.
#include<iostream>
#include<fstream>
using namespace std;

long long cmmdc(int,int);
void solve(int,int,int&,int&,int&,int&);

int main(){
    freopen("euclid3.in","r",stdin);
    freopen("euclid3.out","w",stdout);

    int T;
    cin>>T;
    long long a,b,c,x,y;

    for(int i=1;i<=T;i++){
        cin>>a>>b>>c;
        int d=cmmdc(a,b);
        if(c%d!=0) cout<<"0 0"<<"\n";
        else{
            int x,y,x0,y0;
            solve(a,b,x,y,x0,y0);
            cout<<x*(c/d)<<" "<<y*(c/d)<<"\n";
        }
    }
}

long long cmmdc(int a,int b){
    if(a%b==0) return b;
    else return cmmdc(b,a%b);
}

void solve(int a,int b,int &x,int &y,int &x0,int &y0){
    if(b==0){
        x0=1;y0=1;
    }else{
        solve(b,a%b,x,y,x0,y0);
        x=y0;
        y=x0-(a/b)*y0;
        x0=x;
        y0=y;
     }

}