Cod sursa(job #143631)

Utilizator alex_dincaDinca Alexandru-Nicolae - UPB alex_dinca Data 26 februarie 2008 18:46:01
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<fstream>     
#include<stdio.h>    
  
using namespace std;    
     
long cmmdc(long a,long b){
    long c;
    while(b){
	c=a%b;
	a=b;
	b=c;
	}
    return a;
}

void euclid(long a, long b, long *d, long *x, long *y){
    if (b==0) {
	*d=a;
	*x=1;
	*y=0;
    } else {
	long x0, y0;
	euclid(b, a%b, d, &x0, &y0);
	*x=y0;
	*y=x0-(a/b)*y0;
    }
}
  
int main(){
ifstream f1("euclid3.in");
ofstream f2("euclid3.out");
int T,i;
long a,b,c,d;
long x,y;
f1>>T;
for(i=0;i<T;i++){
    f1>>a>>b>>c;
    d=cmmdc(a,b);
    if(c%d){
	f2<<0<<' '<<0<<'\n';
	}
    else {
	euclid(a,b,&d,&x,&y);
	c=c/d;
	f2<<x*c<<' '<<y*c<<'\n';
	}
}
  
  
f1.close();   
f2.close();   
  
return 0;}