Cod sursa(job #1468113)

Utilizator dorumusuroiFMI - Doru Musuroi dorumusuroi Data 5 august 2015 11:29:43
Problema Algoritmul lui Euclid extins Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 0.9 kb
#include <stdio.h>
#include <stdlib.h>
//int gcd(int a, int b, int *x, int *y)
//{
//    if(b == 0)
//    {
//        *x = 1;
//        *y = 0;
//        return a;
//    }
//    int x0, y0, D;
//    D = gcd(b, a%b, &x0, &y0);
//    *x = y0;
//    *y = x0 - (a/b)*y0;
//    return D;
//}
int gcd( int A, int B, int *X, int *Y )
{
    if (B == 0)
    {
        *X = 1;
        *Y = 0;
        return A;
    }

    int X0, Y0, D;
    D = gcd( B, A % B, &X0, &Y0 );

    *X = Y0;
    *Y = X0 - (A / B) * Y0;
    return D;
}
int main()
{
    freopen("euclid3.in","r", stdin);
    freopen("euclid3.out","w", stdout);
    int a, b, d, x, y, c, t;
    for(scanf("%d",&t); t>0; t--)
    {
        scanf("%d %d %d", &a,&b,&c);
        d = gcd(a,b,&x,&y);
        if(c%d)
            printf("0 0\n");
        else
            printf("%d %d\n", x*(c/d), y*(c/d));
    }
    return 0;
}