Cod sursa(job #1920411)

Utilizator cyber_ghSoltan Gheorghe cyber_gh Data 10 martie 2017 00:18:40
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ifstream fin("euclid3.in");
ofstream fout("euclid3.out");
ll gcdext(ll a,ll b,ll &x,ll &y){
    if (b==0){
        x=1;
        y=0;
        return a;


    }
    ll x1,y1,gcd=gcdext(b,a%b,x1,y1);
    x=y1;
    y=x1-(a/b)*y1;
    return gcd;
}

void solvethisshit(ll a,ll b ,ll c){
    if (c%__gcd(a,b)!=0){
        fout <<"0 0"<<"\n";
        return ;

    }
    ll p=__gcd(a,b);
    a/=p;
    b/=p;
    c/=p;
    ll x=0,y=0;
    gcdext(a,b,x,y);
    x*=c;
    y*=c;
    fout <<x<<" "<<y<<"\n";
    return ;
}


int main()
{


   int T;
   fin >>T;
   //cout <<T;
   for (int i=1;i<=T;i++){
    ll a,b,c;
    fin >>a>>b>>c;
    //cout <<a<<" "<<b<<" "<<c<<endl;
    solvethisshit(a,b,c);

   }
    return 0;
}