当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

3948:Common Polynomial

题目描述
Math teacher Mr. Matsudaira is teaching expansion and factoring of polynomials to his students. Last week he instructed the students to write two polynomials (with a single variable x), and to report GCM (greatest common measure) of them as a homework, but he found it boring to check their answers manually. So you are asked to write a program to check the answers.
Hereinafter, only those polynomials with integral coefficients, called integral polynomials, are considered.
When two integral polynomials A and B are given, an integral polynomial C is a common factor of A and B if there are some integral polynomials X and Y such that A = CX and B = CY.
GCM of two integral polynomials is a common factor which has the highest degree (for x, here); you have to write a program which calculates the GCM of two polynomials.
It is known that GCM of given two polynomials is unique when constant multiplication factor is ignored. That is, when C and D are both GCM of some two polynomials A and B, p×C = q×D for some nonzero integers p and q.
输入解释
The input consists of multiple datasets. Each dataset constitutes a pair of input lines, each representing a polynomial as an expression defined below.


A primary is a variable x, a sequence of digits 0 - 9, or an expression enclosed within ( ... ). Examples: x, 99, (x+1).
A factor is a primary by itself or a primary followed by an exponent. An exponent consists of a symbol ^ followed by a sequence of digits 0 - 9. Examples: x^05, 1^15, (x+1)^3.
A term consists of one or more adjoining factors. Examples: 4x, (x+1)(x-2), 3(x+1)^2.
An expression is one or more terms connected by either + or -. Additionally, the first term of an expression may optionally be preceded with a minus sign -. Examples: -x+1, 3(x+1)^2-x(x-1)^2.


Integer constants, exponents, multiplications (adjoining), additions (+) and subtractions/negations (-) have their ordinary meanings. A sequence of digits is always interpreted as an integer constant. For example, 99 means 99, not 9 × 9.
Any subexpressions of the input, when fully expanded normalized, have coefficients less than 100 and degrees of x less than 10. Digit sequences in exponents represent non-zero values.
All the datasets are designed so that a standard algorithm with 32-bit two’s complement integers can solve the problem without overflows.
The end of the input is indicated by a line containing a period.
输出解释
For each of the dataset, output GCM polynomial expression in a line, in the format below.


c0x^p0 ± c1x^p1 ... ± cnx^pn


Where ci and pi (i = 0, ... , n) are positive integers with p0 > p1 > ... > pn, and the greatest common divisor of {ci | i = 0, ... , n} is 1.
Additionally:


When ci is equal to 1, it should be omitted unless corresponding pi is 0,
x^0 should be omitted as a whole, and
x^1 should be written as x.

输入样例
-(x^3-3x^2+3x-1)
(x-1)^2
x^2+10x+25
x^2+6x+5
x^3+1
x-1
.
输出样例
x^2-2x+1
x+5
1

该题目是Virtual Judge题目,来自 北京大学POJ

源链接: POJ-3948

最后修改于 2020-10-29T07:16:30+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 65536