Cod sursa(job #1096649)

Utilizator dropsdrop source drops Data 2 februarie 2014 14:34:27
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
/* Calculeaza perechea (x, y) care satisface relatia Ax + By = gcd(A, B) */
#include <stdio.h>

struct Group
{
    int X, Y;
    Group(int X0 = 0, int Y0 = 0)
    {
        this->X = X0;
        this->Y = Y0;
    }
};

Group operator-(Group A, Group B)
{
        Group C;
        C.X = A.X - B.X;
        C.Y = A.Y - B.Y;
        return C;
}
Group operator*(Group A, int Q)
{
    A.X *= Q;
    A.Y *= Q;
    return A;
}

int T, A, B, C, A1;

int main()
{
    freopen("euclid3.in","r",stdin);
    freopen("euclid3.out","w",stdout);
    scanf("%d", &T);
    while(T--)
    {
        Group Va(1, 0), Vb(0, 1), Vr;

        scanf("%d %d %d", &A, &B, &C);

        while (B != 0)
        {
            Vr = Va - Vb * (A / B);
            A1 = A;
            A = B;
            B = A1 % B;
            Va = Vb;
            Vb = Vr;
        }
        if (C % A != 0)
        {
            printf("0 0\n");
        }
        else
        {
            printf("%d %d\n", Va.X * (C/A), Va.Y * (C/A));
        }
    }
}