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

決賽題目

包含變數 x,y,z 的多項式是指由 x^i y^j z^k 的線性組合（x^i 表示 x 的 i 次方），其中之 i,j,k, 為非負的整數。本題只考慮係數為整數的 x,y,z 多項式。寫一程式計算兩多項式的加、減、乘、除，以及分解因式的運算。

輸入檔說明

輸入檔案可能包含許多指令：

• Add(p1,p2)：將兩多項式 p1 和 p2 相加。
• Sub(p1,p2)：將兩多項式 p1 和 p2 相減。
• Mul(p1,p2)：將兩多項式 p1 和 p2 相乘。
• Div(p1,p2)：將兩多項式 p1 和 p2 相除，得到商 Q 以及餘式 R。
• Fac(P1)：將多項式 p1 分解因式。
• Exit：結束

為簡單起見，Div(p1,p2) 和 Fac(p1) 中的多項式僅包含一個變數 x，Div(p1,p2) 中的 p2 的最高項係數為 1，Fac(p1) 中的 p1 為 x 的 2 次式或 3 次式，且其最高項的係數為 1。每個式子中間不會有空白。

輸出檔說明

針對每一個指令，印出原指令，以及計算的結果，在做因式分解時，每個因式的係數都必須為整數。印出結果時應依照 x^i y^j z^k 中 i+j+k 的大小由大到小排列，i+j+k 的大小相同時，依照 i 的大小排列，i 的值相同時，再依照 j 的大小排列，若 i, j 的值都相同時，再依照 k 的大小排列。輸出時，每組答案間不可有空白行，式子中間也不可以有空白，等號兩邊最前面的數字前面也不可以有正號。一次項不輸出 ^1，即輸出 2x 而非 2x^1；零次項不輸出，即輸出 2 而非 2x^0。係數為 0 的項不輸出。零多項式則輸出 0。因式分解方面，若不能分解，則直接輸出原式；若可分解，則以括弧括住，且同項需合併。如 (x+1)(x+1) 應輸出為 (x+1)^2。

範例

Add(x^2+y^2,2xy)
Sub(x^2,3xy)
Mul(x+y,x+y)
Div(x^3-1,x-1)
Div(x^3-1,x+1)
Fac(x^2-1)
Fac(x^3-1)
Fac(x^2+2)
Exit

Add(x^2+y^2,2xy)=x^2+2xy+y^2
Sub(x^2,3xy)=x^2-3xy
Mul(x+y,x+y)=x^2+2xy+y^2
Div(x^3-1,x-1)=x^2+x+1
Div(x^3-1,x+1)=x^2-x+1...-2
Fac(x^2-1)=(x+1)(x-1)
Fac(x^3-1)=(x-1)(x^2+x+1)
Fac(x^2+2)=x^2+2