Cod sursa(job #2289449)

Utilizator gabiluciuLuciu Gabriel gabiluciu Data 24 noiembrie 2018 16:52:38
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>
#define  nl '\n'
using namespace std;
int cmmdc(int a,int b,int &x, int &y) {
    if(!b){
        x=1;
        y = 0;
        return a;
    }
    else{
        int x0,y0,c,d;
        d = cmmdc(b,a%b,x0,y0);
        c = a/b;
        x = y0;
        y = x0 - c * y0;
        return  d;
    }
}
int main() {
    freopen("euclid3.in","r",stdin);
    freopen("euclid3.out","w",stdout);
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    for(int i=0;i<n;++i){
        int a,b,d,x,y;
        cin >> a >> b >> d;
        int c = cmmdc(a,b,x,y);
        ///cout << c << nl;
        if(d%c) cout << 0 << ' ' << 0 << nl;
        else {
            c = d/c;
            cout << x*c << ' ' << y*c << nl;
        }

    }
    return 0;
}