Cod sursa(job #1471131)

Utilizator Theodor1000Cristea Theodor Stefan Theodor1000 Data 13 august 2015 10:56:56
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <cstdio>
#include <algorithm>

using namespace std;

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

    int t;
    scanf ("%d", &t);

    for (; t; --t)
    {
        int a, b, c;
        scanf ("%d %d %d", &a, &b, &c);

        bool OK = false;
        if (a < b) swap (a, b), OK = true;

        int x0 = 1, x = 0, y0 = 0, y = 1;
        while (b)
        {
            int r = a % b;
            int c = a / b;
            int cb = b;
            b = r;
            a = cb;

            int cx = x;
            x = x0 - c * x;
            x0 = cx;

            int cy = y;
            y = y0 - c * y;
            y0 = cy;
        }

        if (c % a)
        {
            printf ("0 0\n");
            continue;
        }

        if (OK) swap (x0, y0);
        printf ("%d %d\n", c / a * x0, c / a * y0);
    }

    return 0;
}