Cod sursa(job #3356733)

Utilizator Marius08Marius Benea Marius08 Data 3 iunie 2026 19:22:30
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <stdio.h>

long long euclid_extins(long long a, long long b, long long *x, long long *y) {
    if (b == 0) { // cmmdc = a
        *x = 1;
        *y = 0;
        return a;
    }

    long long x1, y1;
    long long cmmdc = euclid_extins(b, a%b, &x1, &y1);
    long long c = a/b;
    *x = y1;
    *y = x1 - c * y1;
    return cmmdc;
}

long long ecuatie(long long a, long long b, long long c, long long *x, long long *y) {
    long long x1, y1;
    long long d = euclid_extins(a,b,&x1,&y1);
    if(c % d != 0)
        return 0;
    *x = x1 * (c/d);
    *y = y1 * (c/d);
    return 1;
}

int main() {
    FILE *fin = NULL;
    fin = fopen("euclid3.in","r");
    if(fin == NULL)
        return -1;
    FILE *fout = NULL;
    fout = fopen("euclid3.out", "w");
    int n;
    long long a, b, c;
    fscanf(fin, "%d", &n);
    for(int i = 1; i <= n; i ++) {
        long long x, y;
        fscanf(fin, "%lld %lld %lld", &a, &b, &c);
        int ok = ecuatie(a,b,c,&x,&y);
        if(ok == 1)
            fprintf(fout, "%lld %lld\n", x, y);
        else
            fprintf(fout,"0 0\n");
    }
    
    fclose(fin);
    fclose(fout);
    return 0;
}