Cod sursa(job #2480211)

Utilizator gazdac_alex@yahoo.comGazdac Alexandru Eugen [email protected] Data 25 octombrie 2019 08:02:46
Problema Floyd-Warshall/Roy-Floyd Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
/*
========================= EXPLICARE MATEMATICA ================================
 
 a*x + b*y = c;

 Fie d = cmmdc(a,b);
 Ca ecuatia sa aiba solutie, c = d sau c = d * k pentru oricare k intreg =>
 a*x + b*y = d; (1)

 Fie a*x0 + b*y0 = d;
 
 Din euclid =>
 Daca b = 0 atunci y0 = 0 si x0 = 1;

 b*x0 + (a%b)*y0 = d;

 Fie c=a/b => 
 a%b = a-b*c =>

 b*x0 + (a-b*c)*y0 = d; (2)
 
 1,2 => b*x0 + (a-b*c)*y0 = a*x + b*y;
		b*(x0 - c*y0 - y) = a*(x - y0);
		=> y = x0 - c*y0;
		   x = y0
 */

#include <iostream>
#include <fstream>
using namespace std;
ifstream in("euclid3.in");
ofstream out("euclid3.out");


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

int main()
{
	int n, a, b, c, d, x, y;
	in >> n;
	for (int i = 1; i <= n; i++) {
		in >> a >> b >> c;
		euclid_extins(&d, a, b, &x, &y);
		if (c % d) {
			out << "0 0" << '\n';
		}
		else {
			out << x*(c/d)  << " " << y*(c/d) << "\n";
		}
	}
}