Irreducible Polynomial - 题解

标签与难度

标签: 数学, 多项式, 代数基本定理, 判别式, 入门 难度: 900

题目大意喵~

主人你好呀~ 这道题是关于一个叫做“多项式”的数学概念的喵。

题目会给我们一个 $n$ 次多项式，它的系数都是整数，形式如下：

$$P(x) = a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0$$

我们需要判断这个多项式在实数范围内是不是“不可约”的。

“不可约”是什么意思呢？简单来说，就是一个多项式不能被分解成两个或更多个次数更低、系数也为实数的多项式的乘积。

比如说，$x^2+1$ 就是不可约的，因为你没法在实数范围内把它分解开。但是 $x^2-1$ 就不是不可约的，因为它可以分解成 $(x-1)(x+1)$，对吧？

输入格式:

• 第一行是一个整数 $T$，表示有 $T$ 组测试数据。
• 每组数据第一行是一个整数 $n$，表示多项式的次数。
• 第二行是 $n+1$ 个整数，从 $a_0$ 到 $a_n$ 依次给出多项式的系数。

输出格式:

• 对每组数据，如果多项式是不可约的，就输出 "Yes"；否则输出 "No"。

解题思路分析

喵哈哈~ 这道题看起来很数学，可能会吓到一些小可爱，但别怕，我来给你分析一下，其实它背后是一个非常优美的数学定理，一旦理解了，问题就迎刃而解啦！

这个核心的定理叫做 代数基本定理 (Fundamental Theorem of Algebra)。

这个定理告诉我们一个惊人的事实：在复数范围内，任何一个次数不小于1的多项式都至少有一个复数根。由此可以推导出，一个 $n$ 次多项式恰好有 $n$ 个复数根（包括重根）。

但是题目要求的是在实数范围内判断不可约性。这和复数根有什么关系呢？

关系可大着呢！对于一个系数全是实数的多项式（就像我们题目里的一样），它的复数根有一个很可爱的特性：如果一个复数 $z = a+bi$ (这里 $b \neq 0$) 是它的根，那么这个复数的共轭 $\bar{z} = a-bi$ 也一定是它的根！它们总是成双成对地出现，就像我和我的尾巴一样，喵~

于是，任何实系数多项式都可以被分解成两种因式的乘积：

1. 线性因式: $(x-r)$，其中 $r$ 是一个实数根。
2. 二次因式: $(x-z)(x-\bar{z}) = x^2 - (z+\bar{z})x + z\bar{z}$。这是一个系数为实数的二次多项式，并且因为它没有实数根（它的根是共轭复数嘛），所以它在实数范围内是不可约的。

有了这个强大的理论武器，我们就可以分情况讨论多项式的次数 $n$ 了：

情况一：$n \geq 3$

如果一个多项式的次数 $n \geq 3$，它还能是不可约的吗？

• 如果 $n$ 是奇数（比如3, 5, ...），它的复数根不能全部成双成对出现，所以至少会有一个落单的实数根 $r$。只要有实数根，多项式就可以分解出 $(x-r)$ 这个因式，所以它一定是可约的。
• 如果 $n$ 是偶数（比如4, 6, ...），它可以被分解成若干个二次不可约因式的乘积。例如，一个4次多项式可以分解成两个2次多项式的乘积。所以，它也一定是可约的。

结论：只要多项式的次数 $n \geq 3$，它在实数范围内就一定是可约的。直接输出 "No" 就好啦！

情况二：$n=0$ 或 $n=1$

• $n=0$: 这是一个常数 $a_0$。它不能被分解成次数更低的多项式（因为没有比0更低的非负次数了），所以它是不可约的。
• $n=1$: 这是一个一次多项式 $a_1x + a_0$。它代表一条直线，已经是最简单的多项式形式了，无法再分解。所以它也是不可约的。

结论：当 $n \le 1$ 时，多项式是不可约的。输出 "Yes"！

情况三：$n=2$

这是最有趣的情况了，喵~ 一个二次多项式 $a_2x^2 + a_1x + a_0$。 根据我们前面的分析，它要想不可约，就必须没有实数根。 我们怎么判断一个二次方程有没有实数根呢？当然是用我们初中就学过的判别式啦！

$$\Delta = b^2 - 4ac$$

对应到我们的多项式，就是：

$$\Delta = a_1^2 - 4a_2a_0$$

• 如果 $\Delta < 0$，方程没有实数根，多项式在实数范围内不能分解，是不可约的。
• 如果 $\Delta \ge 0$，方程有实数根（一个或两个），多项式可以分解成 $(x-r_1)(x-r_2)$ 的形式，是可约的。

所以，当 $n=2$ 时，我们只要计算判别式的值就可以判断了！

总结一下我们的算法:

1. 读入多项式的次数 $n$ 和它的系数。
2. 如果 $n \geq 3$，输出 "No"。
3. 如果 $n \le 1$，输出 "Yes"。
4. 如果 $n = 2$，计算判别式 $\Delta = a_1^2 - 4a_2a_0$。
   • 如果 $\Delta < 0$，输出 "Yes"。
   • 否则，输出 "No"。

是不是很简单呀？喵~

代码实现

这是我根据上面的思路，为你精心准备的一份代码。注释很详细，希望能帮到你，呐~

#include <iostream>
#include <vector>
#include <numeric>

// 为了让代码更清晰，我们把每个测试用例的逻辑都放在一个函数里喵
void solve() {
    int n; // 多项式的次数
    std::cin >> n;

    // 使用 vector 来存储系数，比C风格数组更安全方便
    // 系数会按照 a_0, a_1, ..., a_n 的顺序读入
    std::vector<long long> coeffs(n + 1);
    for (int i = 0; i <= n; ++i) {
        std::cin >> coeffs[i];
    }

    // 情况一: 次数大于等于3的多项式在实数域上总是可约的
    if (n >= 3) {
        std::cout << "No" << std::endl;
        return;
    }

    // 情况二: 0次和1次多项式总是不可约的
    if (n <= 1) {
        std::cout << "Yes" << std::endl;
        return;
    }

    // 情况三: 2次多项式，需要通过判别式来判断
    if (n == 2) {
        // P(x) = a_2*x^2 + a_1*x + a_0
        // coeffs[0] = a_0, coeffs[1] = a_1, coeffs[2] = a_2
        long long a0 = coeffs[0];
        long long a1 = coeffs[1];
        long long a2 = coeffs[2];

        // 计算判别式 Delta = a_1^2 - 4*a_2*a_0
        // 注意！系数的范围可能很大，直接相乘可能会溢出int
        // 所以我们用 long long 来计算，并且在乘法时最好显式转换一下
        long long discriminant = a1 * a1 - 4LL * a2 * a0;

        if (discriminant < 0) {
            // 判别式小于0，没有实数根，不可约
            std::cout << "Yes" << std::endl;
        } else {
            // 判别式大于等于0，有实数根，可约
            std::cout << "No" << std::endl;
        }
    }
}

int main() {
    // 加速输入输出，让程序跑得更快一点~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t; // 测试数据组数
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

• 时间复杂度: $O(N)$ 对每个测试用例。这里的 $N$ 是多项式的次数。主要的时间开销在于读取 $N+1$ 个系数。判断逻辑本身是 $O(1)$ 的。如果总共有 $T$ 组测试数据，总时间复杂度就是 $O(\sum N)$。

• 空间复杂度: $O(N)$ 对每个测试用例。我们需要一个大小为 $N+1$ 的 vector 来存储系数。

知识点总结

这道题虽然简单，但它背后蕴含的知识点非常重要，值得我们好好回味一下，喵~

1. 代数基本定理: 这是解决问题的理论基石。它告诉我们实系数多项式在实数域上的因式分解结构，即只能分解为一次和二次不可约因式的乘积。
2. 不可约多项式: 我们要清楚地区分不同数域上的不可约性。本题是在实数域 $\mathbb{R}$ 上讨论。一个多项式在 $\mathbb{R}$ 上不可约，不代表它在有理数域 $\mathbb{Q}$ 或复数域 $\mathbb{C}$ 上也如此。在 $\mathbb{C}$ 上，只有一次多项式是不可约的。
3. 二次方程判别式: 这是初等数学中的重要工具，$\Delta = b^2 - 4ac$ 直接决定了二次多项式是否有实数根，从而决定了它在实数域上是否可约。
4. 编程技巧:
   • 分类讨论: 根据问题性质，将复杂问题分解成几个简单的子情况，是解题的常用策略。
   • 注意数据范围: 在进行乘法运算时，要警惕整数溢出。比如本题中，系数可达 $10^9$，a1*a1 会达到 $10^{18}$，4*a2*a0 也会达到这个量级。使用 long long 是非常必要的。

希望这篇题解能帮助你更好地理解这个问题！继续加油哦，主人！喵~