Cod sursa(job #1482983)

Utilizator dec0o0dinu pinu dec0o0 Data 8 septembrie 2015 14:11:39
Problema Algoritmul lui Euclid extins Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
//
//  main.cpp
//  euclid3
//
//  Created by mac-mac on 9/8/15.
//  Copyright (c) 2015 mac-mac. All rights reserved.
//

#include <iostream>
using namespace std;
#include <fstream>

int gcd(int a, int b, int& x, int& y){
    if (b == 0){
        x = 1;
        y = 0;
        return a;
    }else{
        int x0, y0, d;
        d = gcd(b, a % b, x0, y0);
        x = y0;
        y = x0 - (a / b) * y0;
        return d;
    }
}

int main(int argc, const char * argv[]) {
    ifstream cin("euclid3.in");
    ofstream cout("euclid3.out");
        
    int t;
    cin >> t;
    
    int a, b, c, x, y;
    
    while (t--){
        cin >> a;
        cin >> b;
        cin >> c;
        
        if (b > a) swap(a, b);
        int d = gcd(a, b, x, y);
        
        if (c % d)
            cout << "0 0\n";
        else
            cout << (x * (c / d)) << ' ' << (y * (c / d)) << '\n';
    }
    
    cin.close();
    cout.close();
    
    return 0;
}