Cod sursa(job #2180843)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 21 martie 2018 11:22:38
Problema Algoritmul lui Euclid extins Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>

using namespace std;

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

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

int euclid_extins(int a, int b, int &x, int &y){
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    else{
        int d, xa, ya;
        d = euclid_extins(b, a % b, xa, ya);
        x = ya;
        y = xa - (a / b) * ya;
        return d;
    }
}

int cmmdc(int a, int b){
    int r = a % b;
    while(r){
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

int main()
{
    in>>n;
    for(int i = 1; i <= n; ++ i){
        in>>a>>b>>c;
        x = y = 0;
        int C = cmmdc(a, b);
        if(c % C){
            out<<"0 0\n";
            continue;
        }
        euclid_extins(a, b, x, y);
        out<<x * (c / C)<<" "<<y * (c / C)<<'\n';
    }
    return 0;
}