Cod sursa(job #1785167)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 20 octombrie 2016 22:01:52
Problema Algoritmul lui Euclid extins Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.65 kb
#include <stdio.h>

int n, t, a, b, c, d;

void euclid(int a, int b, int* x, int* y, int* d){
    if(b == 0){
        *d = a;
        *x = 1;
        *y = 0;
        return;
    }
    int x0, y0;
    euclid(b, a % b, &x0, &y0, d);
    *y = x0 - (a / b) * y0;
    *x = y0;
}

int main(){
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        scanf("%d%d%d", &a, &b, &c);
        int x, y, d;
        euclid(a, b, &x, &y, &d);

        if(c % d){
            printf("0 0\n");
            continue;
        }

        printf("%d %d\n", x * (c / d), y * (c / d));
    }
    return 0;
}