Cod sursa(job #3357839)

Utilizator poenar_rares_emanuelPoenar Rares Emanuel poenar_rares_emanuel Data 13 iunie 2026 15:50:06
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <stdio.h>
#include <stdlib.h>

long long d;

void euclidExtins(long long a,long long b,long long *x,long long *y){

    if(b==0){
        d=a;
        *x=1;
        *y=0;
        return;
    }

    long long x1,y1;

    euclidExtins(b,a%b,&x1,&y1);

    *x=y1;
    *y=x1-(a / b)*y1;
}

int main(){

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

    int T;
    fscanf(fin,"%d",&T);

    for(int t=0;t<T;t++){

        long long a,b,c;
        fscanf(fin,"%lld %lld %lld",&a,&b,&c);
        if(a==0&&b==0){
            fprintf(fout,"0 0\n");
            continue;
        }
        long long absA=llabs(a);
        long long absB=llabs(b);

        long long x,y;
        euclidExtins(absA,absB,&x,&y);
        if(c%d!=0){
            fprintf(fout,"0 0\n");
            continue;
        }
        long long factor=c/d;
        x=x*factor;
        y=y*factor;

        if(a<0){
            x=-x;
        } 
        if(b<0){
             y=-y;
        }

        fprintf(fout,"%lld %lld\n",x,y);
    }

    fclose(fin);
    fclose(fout);

    return 0;
}