Cod sursa(job #1082952)

Utilizator lorundlorund lorund Data 15 ianuarie 2014 13:06:26
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <cstdio>

int gcd(int a, int b, int *x, int *y){
    int s[3]={1};
    int t[3]={0,1};

    while (b){
        int q=a/b, r=a%b;

        s[2] = s[0]-q*s[1];
        s[0] = s[1];
        s[1] = s[2];

        t[2] = t[0]-q*t[1];
        t[0] = t[1];
        t[1] = t[2];

        a = b;
        b = r;
    }

    if (x){
        *x = s[0];
    }
    if (y){
        *y = t[0];
    }
    return a;
}

int main()
{
    int T;

    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);
    scanf("%d", &T);
    while (T--){
        int a, b, c, x, y, cmmdc;

        scanf("%d %d %d", &a, &b, &c);
        cmmdc = gcd(a, b, &x, &y);
        if (c%cmmdc){
            puts("0 0");
        }
        else{
            x *= c/cmmdc;
            y *= c/cmmdc;
            cmmdc = 1;
            printf("%d %d\n", x/cmmdc, y/cmmdc);
        }
    }
    return 0;
}