Cod sursa(job #2271242)

Utilizator razviii237Uzum Razvan razviii237 Data 28 octombrie 2018 11:54:15
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>

using namespace std;

typedef pair <int, int> pr;

ifstream f("euclid3.in");
ofstream g("euclid3.out");

int t, a, b, d;

// euclid
int e(int a, int b) {
    if(b == 0) {
        return a;
    } else {
        return e(b, a % b);
    }
}

// euclid extins
pr ee(int a, int b, int d) {

    if(b == 0) {
        return {1, 0};
    }
    pr r = ee(b, a % b, d);
    return {r.second, r.first - (a / b) * r.second};
}

int main()
{
    f >> t;

    while(t --) {
        f >> a >> b >> d;
        pr rez = ee(a, b, d);
        int cmmdc = e(a, b);
        if(d % cmmdc == 0) {
            g << ((d / cmmdc) * rez.first) << ' ' << ((d / cmmdc) * rez.second) << '\n';
        } else {
            g << "0 0\n";
        }
    }

    f.close();
    g.close();
    return 0;
}