Cod sursa(job #3357019)

Utilizator Chesa.DavidChesa David Chesa.David Data 5 iunie 2026 00:28:33
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>

typedef long long ll;

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

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 g = extended_gcd(a, b, &x, &y);

        if (c % g != 0) {
            fprintf(fout, "0 0\n");
        } else {
            ll factor = c / g;
            fprintf(fout, "%lld %lld\n", x * factor, y * factor);
        }
    }

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