UVA 684 - Integral Determinant

题目链接

题意：给定一个行列式，求出值

思路：利用线性代数中的列相减，然后不断降阶即可，就是要用分数去写

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 35;

long long gcd(long long a, long long b) {
	if (!b) return a;
	return gcd(b, a % b);
}

long long lcm(long long a, long long b) {
	a = a / gcd(a, b) * b;
	if (a < 0) a = -a;
	return a;
}

struct Fraction {
	long long a, b;
	Fraction() {a = 0; b = 1;}
	
 	Fraction(long long x) {
		a = x; b = 1;
 	}
 	
 	Fraction(long long x, long long y) {
 		a = x; b = y;
  	}
  	
  	void deal() {
  		if (b < 0) {b = -b; a = -a;}
  		long long k = gcd(a, b);
  		if (k < 0) k = -k;
  		a /= k; b /= k;
    }
    
    Fraction operator+(Fraction p) {
    	Fraction ans;
    	ans.b = lcm(b, p.b);
    	ans.a = ans.b / b * a + ans.b / p.b * p.a;
    	ans.deal();
    	return ans;
   	}
   	
   	Fraction operator-(Fraction p) {
    	Fraction ans;
    	ans.b = lcm(b, p.b);
    	ans.a = ans.b / b * a - ans.b / p.b * p.a;
    	ans.deal();
    	return ans;
   	}
   	
   	Fraction operator*(Fraction p) {
   		Fraction ans;
   		ans.a = a * p.a;
   		ans.b = b * p.b;
   		ans.deal();
   		return ans;
   	}
   	
   	Fraction operator/(Fraction p) {
   		Fraction ans;
   		ans.a = a * p.b;
   		ans.b = b * p.a;
   		ans.deal();
   		return ans;
   	}
   	
   	void operator=(long long x) {
   		a = x;
   		b = 1;
   	}
   	
   	void print() {
   		printf("%lld/%lld\n", a, b);
    }
};

int n;

struct Col {
	Fraction r[N];
} c[N];

long long solve() {
	int now = 1;
 	Fraction x = 1;
	for (int now = 1; now < n; now++) {
		int flag = 1;
		for (int i = now - 1; i < n; i++) {
			if (c[i].r[now - 1].a) {
   				swap(c[now - 1], c[i]);
   				if (i != now - 1)
   					x = x * Fraction(-1);
       			flag = 0;
   				break;
			}
  		}
  		if (flag) return 0;
  		flag = 1;
  		for (int i = now; i < n; i++) {
  			Fraction k = c[i].r[now - 1] / c[now - 1].r[now - 1];
  			for (int j = now - 1; j < n; j++)
  				c[i].r[j] = c[i].r[j] - (Fraction(k) * c[now - 1].r[j]);	
    	}
     	x = x * c[now - 1].r[now - 1];
 	}
 	return (x * c[n - 1].r[n - 1]).a;
}

int main() {
	while (~scanf("%d", &n)) {
		if (n == 0) {
			printf("*\n");
			break;
		}
		long long num;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				scanf("%lld", &num);
				c[j].r[i] = num;
   			}
  		}
  		printf("%lld\n", solve());
 	}
	return 0;
}