prithivMLmods/Coder-Stat

1 2<H1><font color="#000">Problem I:</font> Common Polynomial</H1>3 4<p>5Math teacher Mr. Matsudaira is teaching expansion and factoring of polynomials to his students.6Last week he instructed the students to write two polynomials (with a single variable x), and7to report GCM (greatest common measure) of them as a homework, but he found it boring to8check their answers manually. So you are asked to write a program to check the answers.9</p>10<p>11Hereinafter, only those polynomials with integral coefficients, called integral polynomials, are12considered.13</p>14<p>15When two integral polynomials <i>A</i> and <i>B</i> are given, an integral polynomial <i>C</i> is a common factor16of <i>A</i> and <i>B</i> if there are some integral polynomials <i>X</i> and <i>Y</i> such that <i>A</i> = <i>CX</i> and <i>B</i> = <i>CY</i>.17</p>18<p>19GCM of two integral polynomials is a common factor which has the highest degree (for <i>x</i>, here);20you have to write a program which calculates the GCM of two polynomials.21</p>22<p>23It is known that GCM of given two polynomials is unique when constant multiplication factor is24ignored. That is, when <i>C</i> and <i>D</i> are both GCM of some two polynomials <i>A</i> and <i>B</i>, <i>p</i> &times <i>C</i> = <i>q</i> &times; <i>D</i>25for some nonzero integers <i>p</i> and <i>q</i>.26</p>27 28<H2>Input</H2>29 30<p>31The input consists of multiple datasets. Each dataset constitutes a pair of input lines, each32representing a polynomial as an expression defined below.33</p>34 35<ol>36<li> A <i>primary</i> is a variable x, a sequence of digits 0 - 9, or an expression enclosed within ( ... ). Examples: <pre>x, 99, (x+1)</pre></li>37<li> A <i>factor</i> is a primary by itself or a primary followed by an exponent. An exponent consists38   of a symbol ^ followed by a sequence of digits 0 - 9. Examples: <pre>x^05, 1^15, (x+1)^3</pre></li>39<li> A <i>term</i> consists of one or more adjoining factors. Examples: <pre>4x, (x+1)(x-2), 3(x+1)^2</pre></li>40<li> An <i>expression</i> is one or more terms connected by either + or -. Additionally, the first41   term of an expression may optionally be preceded with a minus sign -. Examples: <pre>-x+1, 3(x+1)^2-x(x-1)^2</pre></li>42</ol>43 44<p>45Integer constants, exponents, multiplications (adjoining), additions (+) and subtractions/negations46(-) have their ordinary meanings. A sequence of digits is always interpreted as an integer con-47stant. For example, 99 means 99, not 9 &times; 9.48 49</p>50 51<p>52Any subexpressions of the input, when fully expanded normalized, have coefficients less than53100 and degrees of x less than 10. Digit sequences in exponents represent non-zero values.54</p>55<p>56All the datasets are designed so that a standard algorithm with 32-bit two’s complement integers57can solve the problem without overflows.58</p>59<p>60The end of the input is indicated by a line containing a period.61</p>62 63 64<H2>Output</H2>65 66<p>67For each of the dataset, output GCM polynomial expression in a line, in the format below.68</p>69<pre>70      <i>c</i><sub>0</sub>x^<i>p</i><sub>0</sub> &plusmn; <i>c</i><sub>1</sub>x^<i>p</i><sub>1</sub> ... &plusmn <i>c</i><sub><i>n</i></sub>x^<i>p</i><sub><i>n</i></sub>71</pre>72<p>73Where <i>c</i><sub><i>i</i></sub> and <i>p</i><sub><i>i</i></sub> (<i>i</i> = 0, . . . , <i>n</i>) are positive integers with <i>p</i><sub>0</sub> &gt; <i>p</i><sub>1</sub> &gt; . . . &gt; <i>p</i><sub><i>n</i></sub>, and the greatest74common divisor of {<i>c</i><sub><i>i</i></sub> | <i>i</i> = 0, . . . , <i>n</i>} is 1.75</p>76<p>77Additionally:78</p>79<ol>80  <li> When <i>c</i><sub><i>i</i></sub> is equal to 1, it should be omitted unless corresponding <i>p</i><sub><i>i</i></sub> is 0,</li>81  <li> x^0 should be omitted as a whole, and</li>82  <li> x^1 should be written as x.</li>83</ol>84 85</p>86 87<H2>Sample Input</H2>88<pre>89-(x^3-3x^2+3x-1)90(x-1)^291x^2+10x+2592x^2+6x+593x^3+194x-195.96</pre>97 98<H2>Output for the Sample Input</H2>99<pre>100x^2-2x+1101x+51021103</pre>104