// gauss.cpp
// Liczy wyznacznik macierzy wymiernych metodą Gaussa.
 
#include <cassert>
#include <cmath>
#include <iostream>
#include <iomanip>
 
using namespace std;
 
class Rational {
    int p, q;   /* p/q,   q > 0 */
public:
	Rational(int p, int q = 1) {
		assert(q != 0);
		if (q < 0) {
			p = -p;
			q = -q;
		}
		int g = gcd(abs(p), q);
 
		this->p = p/g;
		this->q = q/g;
	}
	friend Rational operator+(const Rational &a, const Rational &b) {
		return Rational(a.p*b.q + b.p*a.q,  a.q*b.q);
	}
	friend Rational operator-(const Rational &a, const Rational &b) {
		return Rational(a.p*b.q - b.p*a.q,  a.q*b.q);
	}
	friend Rational operator*(const Rational &a, const Rational &b) {
		return Rational(a.p*b.p, a.q*b.q);
	}
	friend Rational operator/(const Rational &a, const Rational &b) {
		return Rational(a.p*b.q, a.q*b.p);
	}
	friend ostream & operator<<(ostream &out, const Rational &a) {
		out << a.p;
		if (a.q != 1) {
			out << "/" << a.q;
		}
		return out;
	}
	friend bool operator==(const Rational &a, const Rational &b) {
		return a.p == b.p && a.q == b.q;
	}
	friend bool operator!=(const Rational &a, const Rational &b) {
		return a.p != b.p || a.q != b.q;
	}
 
	Rational operator-() const { return Rational(-p, q); }
private:
	int gcd(int a, int b) const {
		int r;
		while (b != 0) {
			r = a % b;
			a = b;
			b = r;
		}
		return a;
	}
};
 
void printMatrix(Rational **A, int n) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << A[i][j] << "\t";
		}
		cout << "\n";
	}
	cout << endl;
}
 
inline void swap(Rational &a, Rational &b) {
	Rational c = a;
	a = b;
	b = c;
}
 
Rational determinant(Rational **A, int n) {
	cout << "Eliminacja Gaussa dla macierzy:\n";
	printMatrix(A,n);
 
	int sign = 1;	
	for (int k = 0; k < n; k++) {		
		if (A[k][k] == 0) {
			for (int s = k+1; s < n; s++) {
				if (A[s][k] != 0) {
					cout << "w" << s+1 << "  <=>  w" << k+1 << "\n";
					for (int j = k; j < n; j++) {
						swap(A[k][j], A[s][j]);
					}
					sign = -sign;
					break;
				}
			}
			if (A[k][k] == 0) {
				cout << "Macierz jest osobliwa." << endl;
				return 0;
			}
			printMatrix(A, n);
		}
 
		bool hasChanged = false;
		for (int i = k+1; i < n; i++) {
			if (A[i][k] != 0) {
				Rational m = A[i][k] / A[k][k];
				cout << "w" << i+1 << "  :=  w" << i+1
				     << " - (" << m << ")*w" << k+1 << "\n";
				for (int j = k; j < n; j++) {
					A[i][j] = A[i][j] - m * A[k][j];
				}
				hasChanged = true;
			}
		}
		if (hasChanged) {
			cout << endl;
			printMatrix(A, n);
		}
	}
	cout << "Eliminacja zakonczona sukcesem!" << endl;
 
	Rational det = 1;
	for (int k = 0; k < n; k++) {
		det = det * A[k][k];
	}
 
	return sign*det;
}
 
 
int main() {
	Rational A[4][4] = {
		{ 0, 0, 0, 4 },
		{ 0, 2, 0, 0 },
		{ 0, 0, 3, 0 },
		{ 1, 0, 0, 0 },
	};
	Rational *As[4] = { A[0], A[1], A[2], A[3] };
 
	cout << "detA = " << determinant(As, 4) << "\n\n" << endl;
 
 
 
	Rational B[7][7] = {
		{  2, -1,  0,  0,  0,  0,  0 },
		{ -1,  2, -1,  0,  0,  0,  0 },
		{  0, -1,  2, -1,  0,  0,  0 },
		{  0,  0, -1,  2, -1,  0,  0 },
		{  0,  0,  0, -1,  2, -1,  0 },
		{  0,  0,  0,  0, -1,  2, -1 },
		{  0,  0,  0,  0,  0, -1,  2 },
	};
	Rational *Bs[7] = { B[0], B[1], B[2], B[3], B[4], B[5], B[6] };
 
	cout << "detB = " << determinant(Bs, 7) << endl;
 
 
	Rational C[7][7] = {
		{  2, -1,  0,  0,  0,  0, -1 },
		{ -1,  2, -1,  0,  0,  0,  0 },
		{  0, -1,  2, -1,  0,  0,  0 },
		{  0,  0, -1,  2, -1,  0,  0 },
		{  0,  0,  0, -1,  2, -1,  0 },
		{  0,  0,  0,  0, -1,  2, -1 },
		{ -1,  0,  0,  0,  0, -1,  2 },
	};
	Rational *Cs[7] = { C[0], C[1], C[2], C[3], C[4], C[5], C[6] };
 
	cout << "detC = " << determinant(Cs, 7) << endl;
 
 
 
	Rational D[7][7] = {
		{ 1, 2, 3, 4, 5, 6, 7 },
		{ 2, 3, 4, 5, 6, 7, 6 },
		{ 3, 4, 5, 6, 7, 6, 5 },
		{ 4, 5, 6, 7, 6, 5, 4 },
		{ 5, 6, 7, 6, 5, 4, 3 },
		{ 6, 7, 6, 5, 4, 3, 2 },
		{ 7, 6, 5, 4, 3, 2, 1 },
	};
	Rational *Ds[7] = { D[0], D[1], D[2], D[3], D[4], D[5], D[6] };
 
	cout << "detD = " << determinant(Ds, 7) << endl;
 
	return 0;
}
 

Ly8gZ2F1c3MuY3BwCi8vIExpY3p5IHd5em5hY3puaWsgbWFjaWVyenkgd3ltaWVybnljaCBtZXRvZMSFIEdhdXNzYS4KCiNpbmNsdWRlIDxjYXNzZXJ0PgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGlvbWFuaXA+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY2xhc3MgUmF0aW9uYWwgewogICAgaW50IHAsIHE7ICAgLyogcC9xLCAgIHEgPiAwICovCnB1YmxpYzoKCVJhdGlvbmFsKGludCBwLCBpbnQgcSA9IDEpIHsKCQlhc3NlcnQocSAhPSAwKTsKCQlpZiAocSA8IDApIHsKCQkJcCA9IC1wOwoJCQlxID0gLXE7CgkJfQoJCWludCBnID0gZ2NkKGFicyhwKSwgcSk7CgkJCgkJdGhpcy0+cCA9IHAvZzsKCQl0aGlzLT5xID0gcS9nOwoJfQoJZnJpZW5kIFJhdGlvbmFsIG9wZXJhdG9yKyhjb25zdCBSYXRpb25hbCAmYSwgY29uc3QgUmF0aW9uYWwgJmIpIHsKCQlyZXR1cm4gUmF0aW9uYWwoYS5wKmIucSArIGIucCphLnEsICBhLnEqYi5xKTsKCX0KCWZyaWVuZCBSYXRpb25hbCBvcGVyYXRvci0oY29uc3QgUmF0aW9uYWwgJmEsIGNvbnN0IFJhdGlvbmFsICZiKSB7CgkJcmV0dXJuIFJhdGlvbmFsKGEucCpiLnEgLSBiLnAqYS5xLCAgYS5xKmIucSk7Cgl9CglmcmllbmQgUmF0aW9uYWwgb3BlcmF0b3IqKGNvbnN0IFJhdGlvbmFsICZhLCBjb25zdCBSYXRpb25hbCAmYikgewoJCXJldHVybiBSYXRpb25hbChhLnAqYi5wLCBhLnEqYi5xKTsKCX0KCWZyaWVuZCBSYXRpb25hbCBvcGVyYXRvci8oY29uc3QgUmF0aW9uYWwgJmEsIGNvbnN0IFJhdGlvbmFsICZiKSB7CgkJcmV0dXJuIFJhdGlvbmFsKGEucCpiLnEsIGEucSpiLnApOwoJfQoJZnJpZW5kIG9zdHJlYW0gJiBvcGVyYXRvcjw8KG9zdHJlYW0gJm91dCwgY29uc3QgUmF0aW9uYWwgJmEpIHsKCQlvdXQgPDwgYS5wOwoJCWlmIChhLnEgIT0gMSkgewoJCQlvdXQgPDwgIi8iIDw8IGEucTsKCQl9CgkJcmV0dXJuIG91dDsKCX0KCWZyaWVuZCBib29sIG9wZXJhdG9yPT0oY29uc3QgUmF0aW9uYWwgJmEsIGNvbnN0IFJhdGlvbmFsICZiKSB7CgkJcmV0dXJuIGEucCA9PSBiLnAgJiYgYS5xID09IGIucTsKCX0KCWZyaWVuZCBib29sIG9wZXJhdG9yIT0oY29uc3QgUmF0aW9uYWwgJmEsIGNvbnN0IFJhdGlvbmFsICZiKSB7CgkJcmV0dXJuIGEucCAhPSBiLnAgfHwgYS5xICE9IGIucTsKCX0KCQoJUmF0aW9uYWwgb3BlcmF0b3ItKCkgY29uc3QgeyByZXR1cm4gUmF0aW9uYWwoLXAsIHEpOyB9CnByaXZhdGU6CglpbnQgZ2NkKGludCBhLCBpbnQgYikgY29uc3QgewoJCWludCByOwoJCXdoaWxlIChiICE9IDApIHsKCQkJciA9IGEgJSBiOwoJCQlhID0gYjsKCQkJYiA9IHI7CgkJfQoJCXJldHVybiBhOwoJfQp9OwoKdm9pZCBwcmludE1hdHJpeChSYXRpb25hbCAqKkEsIGludCBuKSB7Cglmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewoJCWZvciAoaW50IGogPSAwOyBqIDwgbjsgaisrKSB7CgkJCWNvdXQgPDwgQVtpXVtqXSA8PCAiXHQiOwoJCX0KCQljb3V0IDw8ICJcbiI7Cgl9Cgljb3V0IDw8IGVuZGw7Cn0KCmlubGluZSB2b2lkIHN3YXAoUmF0aW9uYWwgJmEsIFJhdGlvbmFsICZiKSB7CglSYXRpb25hbCBjID0gYTsKCWEgPSBiOwoJYiA9IGM7Cn0KClJhdGlvbmFsIGRldGVybWluYW50KFJhdGlvbmFsICoqQSwgaW50IG4pIHsKCWNvdXQgPDwgIkVsaW1pbmFjamEgR2F1c3NhIGRsYSBtYWNpZXJ6eTpcbiI7CglwcmludE1hdHJpeChBLG4pOwoJCglpbnQgc2lnbiA9IDE7CQoJZm9yIChpbnQgayA9IDA7IGsgPCBuOyBrKyspIHsJCQoJCWlmIChBW2tdW2tdID09IDApIHsKCQkJZm9yIChpbnQgcyA9IGsrMTsgcyA8IG47IHMrKykgewoJCQkJaWYgKEFbc11ba10gIT0gMCkgewoJCQkJCWNvdXQgPDwgInciIDw8IHMrMSA8PCAiICA8PT4gIHciIDw8IGsrMSA8PCAiXG4iOwoJCQkJCWZvciAoaW50IGogPSBrOyBqIDwgbjsgaisrKSB7CgkJCQkJCXN3YXAoQVtrXVtqXSwgQVtzXVtqXSk7CgkJCQkJfQoJCQkJCXNpZ24gPSAtc2lnbjsKCQkJCQlicmVhazsKCQkJCX0KCQkJfQoJCQlpZiAoQVtrXVtrXSA9PSAwKSB7CgkJCQljb3V0IDw8ICJNYWNpZXJ6IGplc3Qgb3NvYmxpd2EuIiA8PCBlbmRsOwoJCQkJcmV0dXJuIDA7CgkJCX0KCQkJcHJpbnRNYXRyaXgoQSwgbik7CgkJfQoJCQoJCWJvb2wgaGFzQ2hhbmdlZCA9IGZhbHNlOwoJCWZvciAoaW50IGkgPSBrKzE7IGkgPCBuOyBpKyspIHsKCQkJaWYgKEFbaV1ba10gIT0gMCkgewoJCQkJUmF0aW9uYWwgbSA9IEFbaV1ba10gLyBBW2tdW2tdOwoJCQkJY291dCA8PCAidyIgPDwgaSsxIDw8ICIgIDo9ICB3IiA8PCBpKzEKCQkJCSAgICAgPDwgIiAtICgiIDw8IG0gPDwgIikqdyIgPDwgaysxIDw8ICJcbiI7CgkJCQlmb3IgKGludCBqID0gazsgaiA8IG47IGorKykgewoJCQkJCUFbaV1bal0gPSBBW2ldW2pdIC0gbSAqIEFba11bal07CgkJCQl9CgkJCQloYXNDaGFuZ2VkID0gdHJ1ZTsKCQkJfQoJCX0KCQlpZiAoaGFzQ2hhbmdlZCkgewoJCQljb3V0IDw8IGVuZGw7CgkJCXByaW50TWF0cml4KEEsIG4pOwoJCX0KCX0KCWNvdXQgPDwgIkVsaW1pbmFjamEgemFrb25jem9uYSBzdWtjZXNlbSEiIDw8IGVuZGw7CgkKCVJhdGlvbmFsIGRldCA9IDE7Cglmb3IgKGludCBrID0gMDsgayA8IG47IGsrKykgewoJCWRldCA9IGRldCAqIEFba11ba107Cgl9CgkKCXJldHVybiBzaWduKmRldDsKfQoKCmludCBtYWluKCkgewoJUmF0aW9uYWwgQVs0XVs0XSA9IHsKCQl7IDAsIDAsIDAsIDQgfSwKCQl7IDAsIDIsIDAsIDAgfSwKCQl7IDAsIDAsIDMsIDAgfSwKCQl7IDEsIDAsIDAsIDAgfSwKCX07CglSYXRpb25hbCAqQXNbNF0gPSB7IEFbMF0sIEFbMV0sIEFbMl0sIEFbM10gfTsKCQoJY291dCA8PCAiZGV0QSA9ICIgPDwgZGV0ZXJtaW5hbnQoQXMsIDQpIDw8ICJcblxuIiA8PCBlbmRsOwoJCgkKCQoJUmF0aW9uYWwgQls3XVs3XSA9IHsKCQl7ICAyLCAtMSwgIDAsICAwLCAgMCwgIDAsICAwIH0sCgkJeyAtMSwgIDIsIC0xLCAgMCwgIDAsICAwLCAgMCB9LAoJCXsgIDAsIC0xLCAgMiwgLTEsICAwLCAgMCwgIDAgfSwKCQl7ICAwLCAgMCwgLTEsICAyLCAtMSwgIDAsICAwIH0sCgkJeyAgMCwgIDAsICAwLCAtMSwgIDIsIC0xLCAgMCB9LAoJCXsgIDAsICAwLCAgMCwgIDAsIC0xLCAgMiwgLTEgfSwKCQl7ICAwLCAgMCwgIDAsICAwLCAgMCwgLTEsICAyIH0sCgl9OwoJUmF0aW9uYWwgKkJzWzddID0geyBCWzBdLCBCWzFdLCBCWzJdLCBCWzNdLCBCWzRdLCBCWzVdLCBCWzZdIH07CgkKCWNvdXQgPDwgImRldEIgPSAiIDw8IGRldGVybWluYW50KEJzLCA3KSA8PCBlbmRsOwoKCglSYXRpb25hbCBDWzddWzddID0gewoJCXsgIDIsIC0xLCAgMCwgIDAsICAwLCAgMCwgLTEgfSwKCQl7IC0xLCAgMiwgLTEsICAwLCAgMCwgIDAsICAwIH0sCgkJeyAgMCwgLTEsICAyLCAtMSwgIDAsICAwLCAgMCB9LAoJCXsgIDAsICAwLCAtMSwgIDIsIC0xLCAgMCwgIDAgfSwKCQl7ICAwLCAgMCwgIDAsIC0xLCAgMiwgLTEsICAwIH0sCgkJeyAgMCwgIDAsICAwLCAgMCwgLTEsICAyLCAtMSB9LAoJCXsgLTEsICAwLCAgMCwgIDAsICAwLCAtMSwgIDIgfSwKCX07CglSYXRpb25hbCAqQ3NbN10gPSB7IENbMF0sIENbMV0sIENbMl0sIENbM10sIENbNF0sIENbNV0sIENbNl0gfTsKCQoJY291dCA8PCAiZGV0QyA9ICIgPDwgZGV0ZXJtaW5hbnQoQ3MsIDcpIDw8IGVuZGw7CgkKCQoJCglSYXRpb25hbCBEWzddWzddID0gewoJCXsgMSwgMiwgMywgNCwgNSwgNiwgNyB9LAoJCXsgMiwgMywgNCwgNSwgNiwgNywgNiB9LAoJCXsgMywgNCwgNSwgNiwgNywgNiwgNSB9LAoJCXsgNCwgNSwgNiwgNywgNiwgNSwgNCB9LAoJCXsgNSwgNiwgNywgNiwgNSwgNCwgMyB9LAoJCXsgNiwgNywgNiwgNSwgNCwgMywgMiB9LAoJCXsgNywgNiwgNSwgNCwgMywgMiwgMSB9LAoJfTsKCVJhdGlvbmFsICpEc1s3XSA9IHsgRFswXSwgRFsxXSwgRFsyXSwgRFszXSwgRFs0XSwgRFs1XSwgRFs2XSB9OwoJCgljb3V0IDw8ICJkZXREID0gIiA8PCBkZXRlcm1pbmFudChEcywgNykgPDwgZW5kbDsKCQoJcmV0dXJuIDA7Cn0K