Cod sursa(job #2180847)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 21 martie 2018 11:24:19
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 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;
        if(a == 0 && c % b == 0){
            out<<"1 "<<c / b<<'\n';
            continue;
        }
        if(b == 0 && c % a == 0){
            out<<c / a<<" 1"<<'\n';
            continue;
        }
        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;
}