[UVA] 10428 - The Roots

題目連結
這題ac uva rank 1耶真是感動到快暴動了










程式碼:
/* 題目: UVa 10428 - The Roots
 * Language: C++
 * Created on: 2016年7月12日
 *   Author: hanting
 */
#include <iostream>
#include <cstring> // memset
#include <iomanip> // setprecision
#include <cmath> // fabs
#include <algorithm> // sort
#include <vector>
#include <cstdio>
using namespace std;
double a[6];
double f(double x) // 高效率求一元多次多項式的值
{
    double result = a[5];
    for(int i = 4; i >= 0; i--)
    {
        result = result * x + a[i];
    }
    return result;
}
double f1(double x)
{
    double result = a[5]*5;
    for(int i = 4; i > 0; i--)
    {
        result = result * x + a[i]*i;
    }
    return result;
}
double newtonsMethod(double x0)
{
    double x1 = x0;
    int cnt = 0;
    do
    {
        if(++cnt == 100) break;
        x0 = x1;
        if(fabs(f(x0)) < 1e-10) return x0;
        x1 = x0 - f(x0)/f1(x0);
    }
    while(fabs(x1 - x0) > 1e-10);
    return x1;
}
void PolynomialDivision(double b, double c) // f div (bx+c)
{
    for(int i = 5; i > 0; i--)
    {
        a[i-1] -= a[i] / b * c;
        a[i] /= b;
    }
    for(int i = 0; i < 5; i++)
    {
        a[i] = a[i+1];
    }
    a[5] = 0;
}
void findRoot(vector<double> &root, int N)
{
    double oneRoot;
    while(root.size() < N)
    {
        oneRoot = newtonsMethod(0);
        root.push_back(oneRoot);
        PolynomialDivision(1, -oneRoot);
    }
}
int main()
{
    int N;
    int caseN = 1;
    while(/*cin >> N*/scanf("%d", &N) == 1 and N)
    {
        memset(a, 0, sizeof(a));
        for(int i = N; i >= 0; i--)
        {
            //cin >> a[i];
            scanf("%lf", a+i);
        }
        vector<double> root;
        findRoot(root, N);
        sort(root.begin(), root.end());
        printf("Equation %d:", caseN++);
        //cout << "Equation " << caseN++ << ":" ;
        for(int i = 0; i < N; i++)
        {
            printf(" %.4lf", root[i]);
            //cout << " " << fixed << setprecision(4) << root[i];
        }
        printf("\n");
        //cout << endl;
    }
    return 0;
}

[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;
}