Cod sursa(job #1021942)

Utilizator danny794Dan Danaila danny794 Data 4 noiembrie 2013 15:01:46
Problema Algoritmul lui Euclid extins Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

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

typedef struct pairs{ int x; int y; } pairs;

int cmmdc(int a, int b){
	if (a == 0 || b == 0)
		return a + b;
	if (a > b) return cmmdc(a % b, b);
	else return cmmdc(a, b % a);
}

pairs euclid_extended(int a, int b){
	pairs result;
	if (b == 1){
		result.x = 0;
		result.y = -1;
	} else if (a == 1){
		result.x = 1;
		result.y = 0;
	} else {
		int d, c;
		pairs rez;
		if(a > b){
			d = a / b;
			c = a % b;
			result = euclid_extended(b, c);
			rez.x = - result.y;
			rez.y = - (result.x + d * result.y);
		} else {
			d = b / a;
			c = b % a;
			result = euclid_extended(a, c);
			rez.y = result.y;
			rez.x = result.x + d * result.y;
		}
		return rez;
	}

	return result;
}

pairs getK(pairs p, int a, int b, int c){
	pairs result;
	int sign = p.x / abs(p.x);
	result.x = p.x;
	result.y = p.y;
	for(int i = 1; i < abs(c); i++){
		result.x+=p.x;
		result.y+=p.y;
		if (abs(result.x) > abs(b)){
			result.x-=sign*b;
			result.y-=sign*a;
		}
	}
	if (c < 0){
		result.x = - result.x;
		result.y = - result.y;
	}

	return result;
}

void solve(int a, int b, int c){
	int cm = cmmdc(abs(a), abs(b));
	if (c % cm != 0)
		g << "0 0\n";
	else{
		a = a / cm;
		b = b / cm;
		c = c / cm;
		pairs p = euclid_extended(abs(a), abs(b));
		p.x = (a / abs(a)) * p.x;
		p.y = (b / abs(b)) * p.y;
		pairs k = getK(p, a, b, c);
		g << k.x << " " << -k.y << '\n';
	}
}

int main() {
	int n, a, b, c;
	f >> n;
	for(int i = 1; i <= n; i++){
		f >> a >> b >> c;
		solve(a, b, c);
	}
	f.close();
	g.close();
	return 0;
}