20130412

#include <stdio.h>
#include <stdlib.h>

typedef long long ll;

void swap(ll * a, ll * b) {
    ll t = *a;
    *a = *b;
    *b = t;
}

int n, sel;
ll ** a, * ans, cm, kk, qq;

int main(void) {
    scanf("%d", &n);
    a = (ll **)malloc(n * sizeof(ll *));
    for (int i = 0; i < n; ++i)
        a[i] = (ll *)malloc((n + 1) * sizeof(ll));
    ans = (ll *)malloc(n * sizeof(ll));
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= n; ++j)
            scanf(LLD, &a[i][j]);
    for (int i = 0; i < n; ++i) {
        sel = i;
        for (int j = i + 1; j < n; ++j)
            if (a[j][i] && (abs(a[j][i]) < abs(a[sel][i]) || !a[sel][i])) sel = j;
        for (int j = 0; j <= n; ++j)
            swap(&a[i][j], &a[sel][j]);
        for (int j = i + 1; j < n; ++j) {
            if (!a[j][i]) continue;
            cm = gcd(a[i][i], a[j][i]);
            kk = a[j][i] / cm;
            qq = a[i][i] / cm;
            for (int k = 0; k <= n; ++k)
                a[j][k] = a[j][k] * qq - a[i][k] * kk;
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        for (int j = i + 1; j < n; ++j)
            a[i][n] -= a[i][j] * ans[j];
        ans[i] = a[i][n] / a[i][i];
    }
    for (int i = 0; i < n; ++i)
        printf("%lld\n", ans[i]);
    for (int i = 0; i < n; ++i)
        free(a[i]);
    free(a);
    free(ans);
    return 0;
}