Cod sursa(job #884076)

Utilizator AndrewTheGreatAndrei Alexandrescu AndrewTheGreat Data 20 februarie 2013 17:18:26
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <stdio.h>

using namespace std;

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

    int N, lastx, lasty, x, y, t, a, b, c, r, xt, yt;
    cin >> N;
    while(N--){
        cin >> a >> b >> c;
        /// I = lastx * a + lasty * b = a
        /// and x * a + y * b = b

        lastx = 1; lasty = 0; x = 0; y = 1;

        while(b != 0) {
            t = a / b;
            r = a % b; a = b; b = r;

            xt = x; yt = y;

            //by reducing the two ecuations: multiply 2nd by t and substract from 1st
            x = lastx - x * t;
            y = lasty - y * t;

            lastx = xt; lasty = yt;
        }

        if(!(c % a))
            cout << (c / a) * lastx << " " << (c / a) * lasty << "\n";
        else cout << "0 0\n";
    }
    return 0;
}