Cod sursa(job #1366020)

Utilizator GilgodRobert B Gilgod Data 28 februarie 2015 17:54:26
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("euclid3.in");
ofstream fout("euclid3.out");

int n, a, b, c;
int x, y;

int euclidExt(int a, int b, int *x, int *y) {
    if (b==0) {
        *x = 1;
        *y = 0;
        return a;     // a*1 + b*0 = a
    }
    int x0 = 0, y0 = 0, d;
    d = euclidExt(b,a%b,&x0,&y0);
    *x = y0;
    *y  = x0 - (a/b)*y0;
    return d;
}

int main()
{
    fin >> n;
    while(n-- > 0) {
        fin >> a >> b >> c;
        int d = euclidExt(a,b,&x,&y);
        if(!(c % d)) fout << x * (c/d) << ' ' << y * (c/d) << endl;
        else fout << "0 0\n";
    }

    fin.close();
    fout.close();
    return 0;
}