多项式生成问题：多多项式相乘求系数及大数场景优化

核心问题 #

• 已知多个多项式的系数列表，如何通过相乘得到最终多项式的系数列表？例如 [1,2] * [1,2] = [1,4,4]（对应多项式 (x+2)(x+2)=x²+4x+4）。
• 解决Codewars题目时，输入根列表返回对应多项式，使用numpy.poly处理大数时误差过大，寻求替代方案。

Codewars题目要求（翻译） #

输入一个根的列表，返回对应的标准形式多项式表达式（例如根为[2,2]时，需返回x² - 4x + 4 = 0）。

原代码问题分析 #

原代码依赖numpy.poly实现，但该函数基于浮点数运算，处理大数时会出现精度丢失，导致系数变为近似值，转整数时出现错误。

解决方案：手动实现整数型多项式乘法 #

每个根r对应一次多项式(x - r)，其系数列表为[1, -r]。我们只需将所有一次多项式的系数依次相乘，全程使用整数运算即可避免精度问题。

多项式乘法逻辑 #

两个多项式系数列表a（长度m）和b（长度n）相乘，结果长度为m+n-1，其中第k项系数为：
sum(a[i] * b[k-i] for i in range(max(0, k-n+1), min(m, k+1)))

修正后的Python代码 #

import re

def multiply_polys(poly1, poly2):
    # 初始化结果多项式，长度为两个多项式长度之和减1
    result = [0] * (len(poly1) + len(poly2) - 1)
    for i in range(len(poly1)):
        for j in range(len(poly2)):
            result[i + j] += poly1[i] * poly2[j]
    return result

def polynomialize(roots):
    # 初始多项式为常数1（空乘积的结果）
    final_coeffs = [1]
    for r in roots:
        # 每个根对应一次多项式 (x - r)，系数为[1, -r]
        linear_poly = [1, -r]
        final_coeffs = multiply_polys(final_coeffs, linear_poly)
    
    # 构造多项式字符串
    terms = []
    degree = len(final_coeffs) - 1
    for power, coeff in enumerate(reversed(final_coeffs)):
        current_power = degree - power
        if coeff == 0:
            continue
        
        # 处理符号
        if terms:
            sign = '+' if coeff > 0 else '-'
            coeff = abs(coeff)
        else:
            sign = '-' if coeff < 0 else ''
            coeff = abs(coeff)
        
        # 处理系数与x的格式
        if current_power == 0:
            term = f"{coeff}"
        elif current_power == 1:
            term = "x" if coeff == 1 else f"{coeff}x"
        else:
            term = f"x^{current_power}" if coeff == 1 else f"{coeff}x^{current_power}"
        
        # 拼接符号与项
        terms.append(f"{sign} {term}" if sign else term)
    
    # 组合所有项并添加等式结尾
    return ' '.join(terms) + ' = 0'

代码说明 #

• multiply_polys：纯整数运算实现多项式乘法，彻底规避浮点数精度问题。
• polynomialize：从根列表出发，逐个生成对应一次多项式并相乘，得到最终整数系数列表后，转换为符合要求的字符串格式。
• 处理了多种特殊情况：系数为1/-1、次数为0/1、符号显示规则等，完全匹配题目输出要求。

测试示例 #

• 输入roots=[2,2]，返回x² - 4x + 4 = 0
• 输入roots=[-3,5]，返回x² - 2x - 15 = 0
• 输入大数根如roots=[10**18, 10**18]，仍能准确返回x² - 2000000000000000000x + 1000000000000000000000000000000000000 = 0

内容的提问来源于stack exchange，提问作者Ashtart