Cod sursa(job #1000858)

Utilizator alexx.cosmaCosma Cristian Alexandru alexx.cosma Data 23 septembrie 2013 20:45:22
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <utility>
using namespace std;

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

struct tripl{
    int x;
    int y;
    int r;
};

tripl euclid(int a, int b)
{
    if (b == 0) {
        tripl p;
        p.x = 1;
        p.y = 0;
        p.r = a;
        return p;
    } else {
        int q = a/b;
        int r = a-b*q;

        tripl p = euclid(b,r);
        tripl res;
        res.x= p.y;
        res.y = p.x - q*p.y;
        res.r = p.r;
        return res;
    }
}

int main()
{
    int nr;

    fin >> nr;

    for(int i=0;i<nr;i++){
        int a,b,d;
        fin >> a;
        fin >> b;
        fin >> d;
        int x,y,r;
        tripl p = euclid(a,b);
        x = p.x;
        y = p.y;
        r = p.r;
        if(!(d%r))
        fout << x*(d/r) << ' ' << y*(d/r) << '\n';
        else
        fout << '0' << ' ' << '0' << '\n';

    }

    return 0;
}