Cod sursa(job #1511477)

Utilizator dan.marculetFII MarculetDan dan.marculet Data 26 octombrie 2015 20:03:34
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>

int t, a, b, c;

typedef long long ll;


int extEuclid(int a, int b, int& x, int& y) {
    if (!b) {
        x = 1;
        y = 0;
        return a;
    }
    
    int x_prec, y_prec, gcd = extEuclid(b, a%b, x_prec, y_prec);
    x = y_prec;
    y = x_prec - (a / b) * y_prec;
    return gcd;
}


int main() {
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);

    scanf("%d", &t);
    while (t--) {
        scanf("%d %d %d", &a, &b, &c);
        int x, y, gcd = extEuclid(a, b, x, y);
        if (c % gcd)
            x = y = 0;
        else {
            x = x * (c / gcd);
            y = y * (c / gcd);
        }
        printf("%d %d\n", x, y);
    }

    return 0;
}