Cod sursa(job #143700)

Utilizator damaDamaschin Mihai dama Data 26 februarie 2008 19:51:20
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <stdio.h>
#include <utility>

#define x first
#define y second

using namespace std;

int div;

pair<int, int> gcd_e(int a, int b)
{
    if(b == 0)
    {
        div = a;
        return make_pair(1, 0);
    }
    else
    {
        pair<int, int> temp = gcd_e(b, a % b);
        int c = a / b;
        return make_pair(temp.y, temp.x - c * temp.y);
    }
}

int main()
{
    freopen("euclid3.in", "r", stdin);
    freopen("euclid3.out", "w", stdout);

    int n, a, b, c, i;
    pair<int, int> temp;

    scanf("%d", &n);

    for(i = 1; i <= n; ++i)
    {
        scanf("%d %d %d", &a, &b, &c);
        temp = gcd_e(a, b);
        //printf("%d\n", div);
        if(c % div != 0)
        {
            printf("0 0\n");
        }
        else
        {
            c /= div;
            printf("%d %d\n", temp.x * c, temp.y * c);
        }
    }

    return 0;
}