Cod sursa(job #3357310)

Utilizator bogdanogrinOGRIN BOGDAN bogdanogrin Data 8 iunie 2026 18:49:20
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <stdio.h>

void extgcd(long long a, long long b, long long *x, long long *y, long long *d) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        *d = a;
        return;
    }
    long long x1, y1;
    extgcd(b, a % b, &x1, &y1, d);
    *x = y1;
    *y = x1 - (a / b) * y1;
}

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

    if (fscanf(fin, "%d", &t) == 1) {
        while (t--) {
            long long a, b, c;
            if (fscanf(fin, "%lld %lld %lld", &a, &b, &c) == 3) {
                long long A = a < 0 ? -a : a;
                long long B = b < 0 ? -b : b;

                if (A == 0 && B == 0) {
                    fprintf(fout, "0 0\n");
                    continue;
                }

                long long x, y, d;
                extgcd(A, B, &x, &y, &d);

                if (c % d != 0) {
                    fprintf(fout, "0 0\n");
                } else {
                    long long mul = c / d;
                    x *= mul;
                    y *= mul;
                    if (a < 0) x = -x;
                    if (b < 0) y = -y;
                    fprintf(fout, "%lld %lld\n", x, y);
                }
            }
        }
    }

    fclose(fin);
    fclose(fout);
    return 0;
}