Cod sursa(job #712612)

Utilizator Sm3USmeu Rares Sm3U Data 13 martie 2012 17:32:36
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <cstdio>

using namespace std;

int t;
int a;
int b;
int c;

int euclid (int a, int b, int &x, int &y)
{
    if (b == 0){
        x = 1;
        y = 0;
        return a;
    }
    int X;
    int Y;
    int D = euclid (b, a % b, X, Y);

    x = Y;
    y = X - (a / b) * Y;
    return D;
}

void citire()
{
    scanf ("%d %d %d", &a, &b, &c);
    int x;
    int y;
    int d = euclid (a, b, x, y);
    if (c % d != 0){
        printf ("0 0\n");
        return;
    }
    printf ("%d %d\n", x * (c / d), y * (c / d));
}

int main()
{
    freopen ("euclid3.in", "r", stdin);
    freopen ("euclid3.out", "w", stdout);
    scanf ("%d", &t);
    while (t --){
        citire();
    }

    return 0;
}