Cod sursa(job #3358421)

Utilizator NeamtuFelixNeamtu Felix NeamtuFelix Data 16 iunie 2026 17:58:11
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <stdio.h>

typedef long long ll;

/* Returneaza gcd(a, b) si gaseste x, y cu a*x + b*y = gcd(a, b) */
ll extended_gcd(ll a, ll b, ll *x, ll *y) {
    if (b == 0) {
        *x = 1; *y = 0;
        return a;
    }

    ll x1, y1;
    ll d = extended_gcd(b, a % b, &x1, &y1);

    /* Reconstructia: x = y1, y = x1 - (a/b)*y1 */
    *x = y1;
    *y = x1 - (a / b) * y1;

    return d;
}

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

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

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

        ll x, y;
        ll d = extended_gcd(a, b, &x, &y); /* acum: a*x + b*y = d */

        /* ecuatia are solutii intregi doar daca d divide c */
        if (c % d != 0) {
            fprintf(fout, "0 0\n");
        } else {
            /* inmultim solutia cu c/d pentru a obtine a*x + b*y = c */
            ll k = c / d;
            fprintf(fout, "%lld %lld\n", x * k, y * k);
        }
    }

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