網際網路程式設計全國大賽

初賽題目

考慮下列 n 個線性方程式︰

a1,1 x1 + a1,2 x2 + ... + a1,n xn = b1
a2,1 x1 + a2,2 x2 + ... + a2,n xn = b2
                    .
                    .
                    .
an,1 x1 + a2,2 x2 + ... + an,n xn = bn

假設有 n 個方程式，則利用高斯消去法可以解出未知數 x1, x2, ..., xn 之值。假設所有的係數 ai,j 以及 bi 都是有理數，其解 x1, x2, ..., xn 也必為有理數。寫一程式，利用高斯消去法求解有理係數的線性方程組。

輸入檔說明

• 輸入資料儲存在檔案 LINEAR.IN 中，此一檔案可能包含許多組線性方程式。每一組線性方程式都由一個正整數 n 開始(n <= 100)，接下來就是 n 個方程式。每一個方程式均含有 n+1 個有理數 ai,1, ai,2, ... ai,n, bi。
• 有理數的表示方式有兩種，第一種為一整數 p，第二種為 p/q，其中 p 和 q 都是整數，且 q>1。
• 最後一組方程式之後會有一個 0，這表示整個資料到此為止，亦即讀到 n=0 時程式即應結束。

輸出檔說明

針對每一組方程式，先印出此方程式，再印出其解。由於方程式間可能線性相依，在此情況下會有無窮多組解或是無解。若此組方程式的解並非唯一，則印出 infinite many solutions。 若此組方程式無解，則印出 no solutions。輸出時，每組答案間要加一行空白，而顯示方程式時，分數要約分，分母為 1 時只印分子，式子中間不可以有空白，等號兩邊最前面的數字前面也不可以有正號。若某一項係數為 0，仍要印出該項，不可省略。

範例

1
2 3
2
1 2 3
2 4 6
2
1 2 3
1 2 4
2
4 -5 8
3 2 12
2
1/2 -2/3 -1
1/4 1/9 3/2
1
0 0
0

2x1=3
x1=3/2

1x1+2x2=3
2x1+4x2=6
infinite many solutions

1x1+2x2=3
1x1+2x2=4
no solutions

4x1-5x2=8
3x1+2x2=12
x1=76/23
x2=24/23

1/2x1-2/3x2=-1
1/4x1+1/9x2=3/2
x1=4
x2=9/2

0x1=0
infinite many solutions