Cod sursa(job #1452360)

Utilizator Emil64Emil Centiu Emil64 Data 20 iunie 2015 17:00:32
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <stdio.h>
#include <assert.h>

using namespace std;

int main()
{
    freopen("euclid3.in", "rt", stdin);
    freopen("euclid3.out", "wt", stdout);

    int T;
    for (scanf("%d", &T), assert( T <= 100 ); T; T--)
    {
        int A, B, C;
        scanf("%d %d %d", &A, &B, &C);

        assert( -1000000000 <= A && A <= 1000000000 );
        assert( -1000000000 <= B && B <= 1000000000 );
        assert( -2000000000 <= C && C <= 2000000000 && C != 0 );

        int D, X = A, Y = B, it = 0, Aux;

        while(B){

            Aux = A % B;
            A = B;
            B = Aux;
            it ++;
        }
        D = A;
        A = X;
        B = Y;
        X = 1;
        Y = 0;

        int x, y, R = A/B;

        for(int i=it; i; --i){

            x = X;
            y = Y;
            X = Y;
            Y = x - R*y;
        }

        if (C % D)
            printf("0 0\n");
        else
            R = C/D , printf("%d %d\n", X * R, Y * R);
    }

    return 0;
}