Cod sursa(job #1988385)

Utilizator b10nd3Oana Mancu b10nd3 Data 2 iunie 2017 21:14:16
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<iostream>
#include<fstream>

using namespace std;

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


int main(){
	ifstream in; ofstream out;
	in.open("euclid3.in"); out.open("euclid3.out");
     
    int t,i;
    long long a,b,c,x,y,d;

    in>>t; 
    for(i=0;i<t;i++){
       in>>a>>b>>c;
       euclid_extins(a,b,&d,&x,&y); 
       if(c%d!=0) out<<0<<" "<<0<<endl;
       else    out<<x*(c/d)<<" "<<y*(c/d)<<endl;
    }

    in.close(); out.close();	
	return 0;
}