Cod sursa(job #1239481)

Utilizator yellowstarTraian Mihai yellowstar Data 9 octombrie 2014 07:51:24
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
//
//  main.cpp
//  euclid3
//
//  Created by Hai Tran Bach on 10/8/14.
//  Copyright (c) 2014 Hai Tran Bach. All rights reserved.
//

#include <iostream>
#include <fstream>

using namespace std;

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

void gcd(int a, int b, int &x, int &y, int &temp) {
    
    if (!b) {
        x = 1;
        y = 0;
        temp = a;
    }
    else {
        int x1 = 0, y1 = 0;
        gcd(b, a % b, x1, y1, temp);
        y = x1 - (a / b) * y1;
        x = y1;
    }
}

int main() {
    
    
    int nr = 0, a = 0, b = 0, c = 0, x = 0, y = 0, temp = 0;
    
    in >> nr;
    
    for (int i = 0; i < nr; ++i) {
        in >> a >> b >> c;
        gcd(a, b, x, y, temp);
        if (c % temp == 0) {
            out << c / temp * x  << " " << c / temp * y << "\n";
        }
        else {
            out << "0 0 \n";
        }
    }
    
    return 0;
}