Cod sursa(job #2049030)

Utilizator alina13mAlinaaa alina13m Data 26 octombrie 2017 19:48:56
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <math.h>

using namespace std;

int N, nr, a, b, c, allNumbers[305], i;

int euclid(int a, int b, int &x, int &y)
{
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    
    }
    
    int x0, y0, d;
    d = euclid(b, a % b, x0, y0);
    x = y0;
    y = x0 - (a / b) * y0;
    //cout << "check d = " << d << endl;  
    return d;
   
}


int main(){

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

	inFile >> N;
	//cout << N << endl;
	
	while(inFile >> nr){
		allNumbers[i] = nr;
		i++;
	}

	for(int j = 0; j < N * 3; j += 3){

		a = allNumbers[j];
		b = allNumbers[j + 1];
		c = allNumbers[j + 2];

		int x, y, d;

		//cout << "check " << a << " " << b << " " << c << " " << endl << endl;

		d = euclid(a, b, x, y);
		
		//cout << "check d = " << d << endl << endl;
		//cout << "double check c/d = " << c/d  << " x = " << x << endl;

		//cout << "check x = " << x << " and y = " << y << endl;
		if(c % d != 0){
			outFile << 0 << " " << 0 << endl;
			//cout << "check " << endl;
		}else{
			outFile << (x * (c / d)) << " " << (y * (c / d)) << endl;
		}

	}

	return 0;

}