Pro.ID21351 TitleFactoring a Polynomial Title链接http://10.20.2.8/oj/exercise/problem?problem_id=21351 AC23 Submit74 Ratio31.08% 时间&空间限制描述Recently Georgie has learned about polynomials. A polynomial in one variable can be viewed as a formal sum anxn + an-1xn-1 + . . . + a1x + a0 , where x is the formal variable and ai are the coefficients of the polynomial. The greatest i such that ai ≠ 0 is called the degree of the polynomial. If ai = 0 for all i, the degree of the polynomial is considered to be -∞. If the degree of the polynomial is zero or -∞, it is called trivial, otherwise it is called non-trivial. What really impressed Georgie while studying polynomials was the fact that in some cases one can apply different algorithms and techniques developed for integer numbers to polynomials. For example, given two polynomials, one may sum them up, multiply them, or even divide one of them by the other. The most interesting property of polynomials, at Georgie's point of view, was the fact that a polynomial, just like an integer number, can be factorized. We say that the polynomial is irreducible if it cannot be represented as the product of two or more non-trivial polynomials with real coefficients. Otherwise the polynomial is called reducible. For example, the polynomial x2 - 2x + 1 is reducible because it can be represented as (x - 1)(x - 1), while the polynomial x2 + 1 is not. It is well known that any polynomial can be represented as the product of one or more irreducible polynomials. Given a polynomial with integer coefficients, Georgie would like to know whether it is irreducible. Of course, he would also like to know its factorization, but such problem seems to be too difficult for him now, so he just wants to know about reducibility. 输入There are several test cases. Every test case has two lines.The first line contains n --- the degree of the polynomial (0 ≤ n ≤ 20). Next line contains n+1 integer numbers, an , an-1 , ..., a1 , a0 --- polynomial coefficients ( -1000 ≤ ai ≤ 1000, an ≠ 0 ). The lase test case contains n = -1, which will not be proceeded. 输出Description Recently Georgie has learned about polynomials. A polynomial in one variable can be viewed as a formal sum anxn + an-1xn-1 + . . . + a1x + a0 , where x is the formal variable and ai are the coefficients of the polynomial. The greatest i such that ai ≠ 0 is called the degree of the polynomial. If ai = 0 for all i, the degree of the polynomial is considered to be -∞. If the degree of the polynomial is zero or -∞, it is called trivial, otherwise it is called non-trivial. What really impressed Georgie while studying polynomials was the fact that in some cases one can apply different algorithms and techniques developed for integer numbers to polynomials. For example, given two polynomials, one may sum them up, multiply them, or even divide one of them by the other. The most interesting property of polynomials, at Georgie's point of view, was the fact that a polynomial, just like an integer number, can be factorized. We say that the polynomial is irreducible if it cannot be represented as the product of two or more non-trivial polynomials with real coefficients. Otherwise the polynomial is called reducible. For example, the polynomial x2 - 2x + 1 is reducible because it can be represented as (x - 1)(x - 1), while the polynomial x2 + 1 is not. It is well known that any polynomial can be represented as the product of one or more irreducible polynomials. Given a polynomial with integer coefficients, Georgie would like to know whether it is irreducible. Of course, he would also like to know its factorization, but such problem seems to be too difficult for him now, so he just wants to know about reducibility. Input There are several test cases. Every test case has two lines.The first line contains n --- the degree of the polynomial (0 ≤ n ≤ 20). Next line contains n+1 integer numbers, an , an-1 , ..., a1 , a0 --- polynomial coefficients ( -1000 ≤ ai ≤ 1000, an ≠ 0 ). The lase test case contains n = -1, which will not be proceeded. Output Output YES if the polynomial given in the input is irreducible and NO in the other case. Sample Input 2 Sample Output NO Source 样例输入2 样例输出NO 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-2 22:42 , Processed in 0.016831 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
