Cod sursa(job #1071638)

Utilizator pitbull007Hurmuzache Ciprian pitbull007 Data 3 ianuarie 2014 11:46:13
Problema Algoritmul lui Euclid extins Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>
#include <stdlib.h>

//se cere aflarea x,y astfel incat a*x+b*y=c; !!! d=c
//*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);

    printf("T=%d\n",T);
    for(i=0;i<T;i++) {
        x=y=cmmdc=0;

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

        euclid_extins(A,B,&cmmdc,&x,&y);
        if(C % cmmdc) {
            fprintf(fout,"0 0");
            printf("\n0 0");
        }else {
            x=x*(C/cmmdc);
            y=y*(C/cmmdc);
            printf("\n%d %d",x,y);
        }
    }


    return 0;
}