Cod sursa(job #3358477)

Utilizator barsescu_andreiBarsescu Andrei Mircea barsescu_andrei Data 16 iunie 2026 23:21:38
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <stdio.h>

long long gcd(long long a, long long b) {
    while (b != 0) {
        long long t = b;
        b = a % b;
        a = t;
    }
    return a;
}

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

void solve(long long a, long long b, long long c, long long *rx, long long *ry) {
    long long d = gcd(a, b);
    if (c % d != 0) {
        *rx = 0;
        *ry = 0;
        return;
    }
    long long x, y;
    extended_gcd(a, b, &x, &y);
    long long k = c / d;
    *rx = x * k;
    *ry = y * k;
}

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

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

    while (t--) {
        long long a, b, c;
        fscanf(fin, "%lld %lld %lld", &a, &b, &c);

        long long x, y;
        solve(a, b, c, &x, &y);
        fprintf(fout, "%lld %lld\n", x, y);
    }

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