Cod sursa(job #3358228)

Utilizator gratian-stefan.tothToth Gratian-Stefan gratian-stefan.toth Data 15 iunie 2026 16:13:02
Problema Algoritmul lui Euclid extins Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <stdio.h>

long long sol(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 g = sol(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--) {
        long long a, b, c;
        fscanf(fin, "%lld %lld %lld", &a, &b, &c);

        long long x, y;
        long long d = sol(a, b, &x, &y);

        if (c % d != 0) {
            /* ecuatia nu are solutie in intregi */
            fprintf(fout, "0 0\n");
        } else {
            /* inmultim solutia particulara cu c/d */
            x = x * (c / d);
            y = y * (c / d);
            fprintf(fout, "%lld %lld\n", x, y);
        }
    }

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