Cod sursa(job #2049047)

Utilizator alina13mAlinaaa alina13m Data 26 octombrie 2017 20:02:09
Problema Algoritmul lui Euclid extins Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>

std::ifstream cin("euclid3.in");
std::ofstream cout("euclid3.out");

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; 
    return d;
   
}


int main(){

	cin >> N;
	
	while(cin >> 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;

		d = euclid(a, b, x, y);

		if(c % d != 0){
			cout << 0 << " " << 0 ;
			cout << "\n";   // de ce nu pot sa pun endl? 
		}else{
			cout << (x * (c / d)) << " " << (y * (c / d));
			cout << "\n";
		}

	}

	return 0;

}