Cod sursa(job #3356350)

Utilizator Sonia.06Braila Sonia Biliana Sonia.06 Data 31 mai 2026 12:22:52
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <stdio.h>
#include <stdlib.h>

long long int euclid_ext(long long int a, long long int b, long long int *X, long long int *Y)
{
    long long int rest, cat, aux;
    long long X0=1, Y0=0;
    long long int X1=0, Y1=1;
    while (b!=0)
    {
        rest=a%b;

        cat=a/b;
        aux=X0-cat*X1;
        X0=X1;
        X1=aux;

        aux=Y0-cat*Y1;
        Y0=Y1;
        Y1=aux;

        a=b;
        b=rest;
    }
    *X=X0;  *Y=Y0;
    return a;
}

int main()
{
    int T;
    long long int a, b, c;
    FILE *f, *g;
    if((f=fopen("euclid3.in", "r"))==NULL)
    {
        fprintf(stderr, "eroare deschidere fisier1\n");
        exit(1);
    }
    if((g=fopen("euclid3.out", "w"))==NULL)
    {
        fprintf(stderr, "eroare deschidere fisier2\n");
        exit(1);
    }
    if(fscanf(f,"%d", &T)!=1)
        return 0;
    for(int i=0; i<T; i++)
    {
        if(fscanf(f,"%lld %lld %lld", &a, &b, &c)!=3)
            return 0;
        long long int X, Y;
        long long int d=euclid_ext(a, b, &X, &Y);
        if(c%d!=0)
        {
            fprintf(g, "0 0\n");
        }
        else
        {
            X=X*(c/d);
            Y=Y*(c/d);
            fprintf(g, "%lld %lld\n", X, Y);
        }
    }
    fclose(f);
    fclose(g);
    return 0;
}