在计算机科学中，多项式乘法是两个或多个多项式的乘积。在Linux系统下，我们可以使用C语言来实现多项式乘法。
多项式表示
在C语言中，多项式通常表示为一个系数数组，其中系数数组的长度等于多项式的阶数加一。例如，一个三阶多项式 ax3 + bx2 + cx + d 的系数数组为 [d, c, b, a] 。
朴素算法
最简单的多项式乘法算法是朴素算法。该算法将两个多项式中的每一项与另一个多项式中的每一项相乘，然后将得到的乘积项相加。对于两个阶数分别为 m 和 n 的多项式，朴素算法的时间复杂度为 O(mn) 。
分治算法
分治算法是多项式乘法的一种更有效的 。该算法将两个多项式递归地分解为较小的多项式，然后分别计算较小多项式的乘积。最后，将较小的乘积组合起来得到最终的多项式乘积。分治算法的时间复杂度为 O(n log n) ，其中 n 是两个多项式中较高阶的多项式的阶数。
FFT算法
FFT（快速傅里叶变换）算法是多项式乘法最快的算法。该算法将多项式表示为复数序列，并利用FFT和IFFT（逆快速傅里叶变换）来计算乘积。FFT算法的时间复杂度为 O(n log n) ，与分治算法相同。
代码示例
以下是一个使用朴素算法实现Linux系统下C语言多项式乘法的代码示例：
c
include
include
int main() {
int m, n;
printf("Enter the degree of the first polynomial: ");
scanf("%d", &m);
printf("Enter the coefficients of the first polynomial: ");
int *a = (int *)malloc((m + 1) * sizeof(int));
for (int i = 0; i <= m; i++) {
scanf("%d", &a[i]);
}
printf("Enter the degree of the second polynomial: ");
scanf("%d", &n);
printf("Enter the coefficients of the second polynomial: ");
int *b = (int *)malloc((n + 1) * sizeof(int));
for (int i = 0; i <= n; i++) {
scanf("%d", &b[i]);
}
int *c = (int *)malloc((m + n + 1) * sizeof(int));
for (int i = 0; i <= m + n; i++) {
c[i] = 0;
}
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
c[i + j] += a[i] * b[j];
}
}
printf("The product of the two polynomials is: ");
for (int i = 0; i <= m + n; i++) {
printf("%dx^%d + ", c[i], i);
}
printf("\n");
return 0;
}
在Linux系统下，我们可以使用朴素算法、分治算法或FFT算法来实现多项式乘法。FFT算法是速度最快的算法，但实现起来也最复杂。对于较小的多项式，朴素算法或分治算法就足够了。
