问题描述

最近，Georgie 学习了关于多项式的知识。一个一元多项式可以表示为一个形式级数：aₙxⁿ + aₙ₋₁xⁿ⁻¹ + ... + a₁x + a₀，其中 x 是形式变量，aᵢ 是多项式的系数。最大的 i 使得 aᵢ ≠ 0 称为多项式的次数。如果所有 aᵢ = 0，则多项式的次数被认为是 -∞。如果多项式的次数是 0 或 -∞，则称其为平凡的（trivial），否则称为非平凡的（non-trivial）。

Georgie 在学习多项式时，最让他印象深刻的是，在某些情况下，可以为多项式应用为整数开发的不同的算法和技术。例如，给定两个多项式，可以将它们相加、相乘，甚至将一个多项式除以另一个多项式。

Georgie 认为多项式最有趣的性质是，多项式可以像整数一样进行因式分解。如果一个多项式不能表示为两个或更多个非平凡多项式的乘积（系数为实数），则称该多项式为不可约的（irreducible）。否则，该多项式称为可约的（reducible）。例如，多项式 x² - 2x + 1 是可约的，因为它可以表示为 (x - 1)(x - 1)，而多项式 x² + 1 是不可约的。众所周知，任何多项式都可以表示为一个或多个不可约多项式的乘积。

给定一个整数系数的多项式，Georgie 想知道它是否是不可约的。当然，他也想知道它的因式分解，但这个问题对他来说现在太难了，所以他只想知道多项式是否可约。

输入格式

输入的第一行包含 n —— 多项式的次数（0 ≤ n ≤ 20）。下一行包含 n + 1 个整数，aₙ, aₙ₋₁, ..., a₁, a₀ —— 多项式的系数（-1000 ≤ aᵢ ≤ 1000，aₙ ≠ 0）。

输出格式

如果输入文件中的多项式是不可约的，则输出 "YES"，否则输出 "NO"。

示例输入 1

2 
1 -2 1 

示例输出 1

NO

来源

Northeastern Europe 2003, Northern Subregion

题意分析

我们需要判断给定的多项式是否是不可约的。根据定义：

1. 不可约多项式：不能表示为两个非平凡多项式（即次数 ≥ 1）的乘积。
2. 可约多项式：可以表示为两个非平凡多项式的乘积。

多项式因式分解的基本理论

对于实系数多项式，不可约多项式只有以下两种形式：

1. 一次多项式（即次数为 1 的多项式，如 ax + b）。
2. 二次多项式，其判别式为负（即没有实数根的多项式，如 x² + 1）。

更高次的多项式（次数 ≥ 3）总是可约的，因为它们可以分解为更低次的多项式的乘积。

解题思路

1. 判断多项式的次数：
   • 如果 n = 0 或 n = 1：多项式是不可约的（根据定义）。
   • 如果 n = 2：检查是否可以分解为两个一次多项式的乘积。即检查判别式 b² - 4ac ≥ 0。如果判别式 ≥ 0，则可约（NO）；否则不可约（YES）。
   • 如果 n ≥ 3：多项式总是可约的（NO）。

示例分析

示例输入 1：

2 
1 -2 1 

• 多项式：x² - 2x + 1。
• 次数：2。
• 判别式：(-2)² - 411 = 4 - 4 = 0 ≥ 0。
• 可以分解为 (x - 1)(x - 1)，因此是可约的。
• 输出：NO。

边界情况

1. n = 0：

   • 多项式为常数（如 5）。
   • 根据定义，是平凡的，不可约。
   • 输出：YES。

2. n = 1：

   • 多项式为一次（如 2x + 3）。
   • 不可约。
   • 输出：YES。

3. n = 2：

   • 需要计算判别式。
   • 如 x² + 1：判别式 0 - 4 = -4 < 0，不可约（YES）。
   • 如 x² - 1：判别式 0 + 4 = 4 > 0，可约（NO）。

4. n ≥ 3：

   • 直接判断为可约（NO）。

代码实现思路

1. 读取 n。
2. 读取多项式系数。
3. 根据 n 的值：
   • n = 0 或 1：输出 "YES"。
   • n = 2：计算判别式（b² - 4ac），判断是否 ≥ 0：
     • 是：输出 "NO"。
     • 否：输出 "YES"。
   • n ≥ 3：输出 "NO"。

解决代码

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> coefficients(n + 1);
    for (int i = 0; i <= n; ++i) {
        cin >> coefficients[i];
    }

    if (n == 0 || n == 1) {
        cout << "YES" << endl;
    } else if (n == 2) {
        int a = coefficients[0];
        int b = coefficients[1];
        int c = coefficients[2];
        int discriminant = b * b - 4 * a * c;
        if (discriminant >= 0) {
            cout << "NO" << endl;
        } else {
            cout << "YES" << endl;
        }
    } else {
        cout << "NO" << endl;
    }

    return 0;
}

代码解释

1. 输入读取：

   • n 是多项式的次数。
   • coefficients 是多项式的系数列表，从最高次到常数项。

2. 处理不同次数的情况：

   • n = 0 或 1：多项式不可约，输出 "YES"。
   • n = 2：计算判别式 b² - 4ac：
     • 如果判别式非负，多项式可约，输出 "NO"。
     • 否则，不可约，输出 "YES"。
   • n ≥ 3：多项式总是可约，输出 "NO"。

这样就能正确判断给定多项式是否不可约。

算法标签

数学 代数 数论