Cod sursa(job #146030)

Utilizator moga_florianFlorian MOGA moga_florian Data 1 martie 2008 08:01:28
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<stdio.h>

int euclid(int a,int b,int &x,int &y){

    if(b==0){
        x=1;y=0;
        return a;
    }
    
    int x0,y0;
    int gcd = euclid(b,a%b,x0,y0);
    
    x = y0;
    y = x0 - (a/b) * y0;
    
    return gcd;

}

int main(){

    FILE *fin = fopen("euclid3.in","r"),
         *fout = fopen("euclid3.out","w");
         
    int T;
    fscanf(fin,"%d",&T);
    
    while(T--){
        int A,B,C,X,Y;
        fscanf(fin,"%d%d%d",&A,&B,&C);
        
        int cmmdc = euclid(A,B,X,Y);
        
        if(C%cmmdc)
            fprintf(fout,"0 0\n");
        else
            fprintf(fout,"%d %d\n", X*(C/cmmdc), Y*(C/cmmdc));
    }
    
    fclose(fin);
    fclose(fout);
    return 0;

}