Cod sursa(job #1071804)

Utilizator pitbull007Hurmuzache Ciprian pitbull007 Data 3 ianuarie 2014 15:02:31
Problema Algoritmul lui Euclid extins Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.95 kb
#include <stdio.h>
#include <stdlib.h>

//se cere aflarea x,y astfel incat a*x+b*y=c; c=cmmdc(a,b).
//*c va fi valoare cmmdc-ului, *x a fi valoare lui x ia *y va fi valoarea calculata pt y.

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

}

int main() {
    FILE *fin,*fout;
    fin=fopen("euclid3.in","r");
    fout=fopen("euclid3.out","w");

    int T,A,B,C,i,x,y,cmmdc;
    fscanf(fin,"%d",&T);

    for(i=0;i<T;i++) {

        fscanf(fin,"%d %d %d",&A,&B,&C);

        euclid_extins(A,B,&cmmdc,&x,&y);    //it's good!
        if(C % cmmdc) {
            fprintf(fout,"\n0 0");
        }else {

            fprintf(fout,"\n%d %d",(x*(C/cmmdc)),(y*(C/cmmdc)));
        }
    }
    fclose(fout);
    fclose(fin);

    return 0;
}