[UVA] 684 - Integral Determinant

題目連結

程式碼:
/* 題目: UVa 684 -  Integral Determinant
 * Language: C++
 * Created on: 2016年7月10日
 *   Author: hanting
 */
#include <iostream>
#include <vector>
using namespace std;
long long gcd(long long a1, long long b1)
{
    unsigned long long a, b;
    if(a1 < 0) a1 *= -1;
    if(b1 < 0) b1 *= -1;
    a = a1;
    b = b1;
    while(a and b)
    {
        (a > b) ? (a %= b) : (b %= a);
    }
    return a ? a : b;
}
long long lcm(long long a, long long b)
{
    return a / gcd(a, b) * b; // a要先/gcd
}
struct Real
{
    long long mom, son;
    Real(int s = 0, int m = 1):mom(m), son(s) {}
    void simple()
    {
        if(mom < 0)
        {
            son *= -1;
            mom *= -1;
        }
        long long _gcd = gcd(mom, son);
        mom /= _gcd;
        son /= _gcd;
    }
    Real operator * (Real b)
    {
        Real result = *this;
        long long gcd1, gcd2;
        gcd1 = gcd(result.mom, b.son);
        gcd2 = gcd(result.son, b.mom);
        result.mom /= gcd1;
        b.son /= gcd1;
        result.son /= gcd2;
        b.mom /= gcd2;
        result.mom *= b.mom;
        result.son *= b.son;
        result.simple();
        return result;
    }
    Real operator / (Real b)
    {
        Real result = *this;
        long long gcd1, gcd2;
        gcd1 = gcd(result.mom, b.mom);
        gcd2 = gcd(result.son, b.son);
        result.mom /= gcd1;
        b.mom /= gcd1;
        result.son /= gcd2;
        b.son /= gcd2;
        result.mom *= b.son;
        result.son *= b.mom;
        result.simple();
        return result;
    }
    void operator -=(Real b)
    {
        long long lcm1 = lcm(mom, b.mom);
        long long a1, b1;
        a1 = lcm1 / mom;
        b1 = lcm1 / b.mom;
        son = son*a1 - b.son*b1;
        mom = lcm1;
        simple();
    }
    void operator *= (Real b)
    {
        long long gcdMom, gcdSon;
        gcdMom = gcd(mom, b.son);
        gcdSon = gcd(son, b.mom);
        mom /= gcdMom;
        b.son /= gcdMom;
        son /= gcdSon;
        b.mom /= gcdSon;

        mom *= b.mom;
        son *= b.son;
        simple();
    }
    void operator /= (Real b)
    {
        long long gcd1, gcd2;
        gcd1 = gcd(mom, b.mom);
        gcd2 = gcd(son, b.son);
        mom /= gcd1;
        b.mom /= gcd1;
        son /= gcd2;
        b.son /= gcd2;
        mom *= b.son;
        son *= b.mom;
        simple();
    }
    friend istream& operator >> (istream &in, Real &r)
    {
        in >> r.son;
        r.mom = 1;
        return in;
    }
    friend ostream& operator << (ostream &out, Real r)
    {
        out << r.son;
        if(r.mom != 1 and r.son) out << '/' << r.mom;
        return out;
    }
};
void doDownTriangle(vector<vector<Real> > &vec) // 讓矩陣對角線以下全變為0
{
    for(int k = 0; k < vec.size(); k++)
    {
        int index = k; // find first element not zero
        while(index < vec.size() and vec[index][k].son == 0) index++;
        if(index == vec.size())
        {
            vec[0][0] = 0;
            return ;
        }
        if(index != k)
        {
            swap(vec[index], vec[k]);
            for(int i = k; i < vec.size(); i++)
            {
                vec[k][i].son *= -1;
            }
        }
        Real tmp = vec[k][k];
        for(int i = k+1; i < vec.size(); i++)
        {
            Real r = vec[i][k] / tmp;
            for(int j = k; j < vec[i].size(); j++)
            {
                vec[i][j] -= vec[k][j] * r;
            }
        }
    }
}
Real Determinant(vector<vector<Real> > &vec)
{
    doDownTriangle(vec);
    Real result(1);
    for(int i = 0; i < vec.size(); i++)
    {
        result *= vec[i][i]; // 因下三角全為0，故對角線乘積為答案
    }
    return result;
}
int main()
{
    int n;
    while(cin >> n and n)
    {
        vector<vector<Real> > matrix(n, vector<Real>(n));
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
                cin >> matrix[i][j];
        }
        cout <<Determinant(matrix) << endl;
    }
    cout << "*" << endl;
    return 0;
}