Cod sursa(job #2483220)

Utilizator OvidRata Ovidiu Ovid Data 29 octombrie 2019 15:31:36
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("euclid3.in"); ofstream fout("euclid3.out"); 



int a, b, c, t;
        
int euclidex(int a, int b, int *x, int *y){
      if(a==0){
         *x =0;
         *y =1;
          return b;
      } 
      else{
        int x1, y1;
        int gcd=euclidex(b%a, a, &x1, &y1); 
        *x=y1-(b/a) * x1;
        *y=x1;
        return gcd;
      } 



}







int main(){
fin>>t;
int g;
int y, x;
 for(int i=0; i<t; i++){
     fin>>a>>b>>c;
     if(abs(c)%__gcd(abs(a), abs(b))>0){fout<<"0 0"<<endl; continue;}

     g=euclidex(a, b, &x, &y);
     x=c/g*x; y=c/g*y;
      fout<<x<<" "<<y<<endl;
 }



    return 0;
}