Cod sursa(job #3232904)

Utilizator INDRIE_FILIPIndrie Filip-Iulian INDRIE_FILIP Data 1 iunie 2024 21:49:33
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <stdio.h>
#include <stdlib.h>

#define fin "euclid3.in"
#define fout "euclid3.out"

int euclid_gcd(int a,int b){
    if(b==0){
        return a;
    }
    return euclid_gcd(b,a%b);
}

void euclid_extins(int a,int b,int *x,int *y){
    int r0=a,r1=b;
    int x0=1,x1=0;
    int y0=0,y1=1;
    while(r1!=0){
        int q=r0/r1,aux;
        aux=r1;
        r1=r0-q*r1;
        r0=aux;

        aux=x1;
        x1=x0-q*x1;
        x0=aux;

        aux=y1;
        y1=y0-q*y1;
        y0=aux;
    }
    *x=x0;
    *y=y0;
}

int main()
{
    FILE *f,*g;
    f=fopen(fin,"r");
    g=fopen(fout,"w");
    int n;
    fscanf(f,"%d",&n);
    for(int i=0;i<n;++i){
        int a,b,c,d;
        fscanf(f,"%d %d %d",&a,&b,&c);
        d=euclid_gcd(a,b);
        if(c%d!=0){
            fprintf(g,"%d %d\n",0,0);
        }
        else{
            int x,y;
            euclid_extins(a,b,&x,&y);
            fprintf(g,"%d %d\n",x*(c/d),y*(c/d));
        }
    }
    fclose(f);
    fclose(g);
    return 0;
}