Cod sursa(job #1389247)

Utilizator casuneanu.andreiCasuneanu Andrei Dan casuneanu.andrei Data 16 martie 2015 09:33:36
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
using namespace std;
#define IN "euclid3.in"
#define OUT "euclid3.out"

ifstream fin(IN);
ofstream fout(OUT);

int n;

int ext(int&, int&, int, int);
void citire();

int main(){
    citire();
    return 0;
}

void citire(){
    fin >>n;

    int i;
    int a, b, c;
    int d, x, y;
    for (i=0; i<n; ++i){
        fin >>a>>b>>c;
        d=ext(x, y, a, b);
        if (c%d)
            fout <<0<<' '<<0<<'\n';
        else
            fout <<c/d*x<<' '<<c/d*y<<'\n';
    }
}

int ext(int &x, int &y, int a, int b){
    if (!b){
        x=1; y=0;
        return a;
    }
    int d=ext(x, y, b, a%b);
    int aux=x;
    x=y;
    y=aux-y*(a/b);
    return d;
}