一元高次方程有理数求解题解

问题分析

给定一个一元 $n$ 次方程 $a_0 + a_1x + a_2x^2 + \ldots + a_nx^n = 0$，要求找出所有的有理数解。

核心思路

基于有理根定理：如果方程有有理数解 $x = \frac{p}{q}$（其中 $p, q$ 互质），那么：

• $p$ 必须是常数项 $a_0$ 的因数
• $q$ 必须是最高次项系数 $a_n$ 的因数

算法详解

1. 有理根定理应用

// 找到第一个非零系数（处理前导零）
int t = 0;
while (arr[t] == 0) t++;

// 分解常数项a0的因数
for (int i = 1; i * i <= abs(arr[t]); i++) {
    if (abs(arr[t]) % i == 0) {
        p1[++cnt1] = i;
        if (i * i != abs(arr[t]) && abs(arr[t]) / i != 0)
            p1[++cnt1] = abs(arr[t]) / i;
    }
}

// 分解最高次项系数an的因数  
for (int i = 1; i * i <= abs(arr[n]); i++) {
    if (abs(arr[n]) % i == 0) {
        p2[++cnt2] = i;
        if (abs(arr[n]) / i != 0 && i * i != abs(arr[n]))
            p2[++cnt2] = abs(arr[n]) / i;
    }
}

2. 候选解生成与验证

for (int i = 1; i <= cnt1; i++) {
    for (int j = 1; j <= cnt2; j++) {
        if (gcd(p1[i], p2[j]) != 1) continue;
        
        // 测试正负两个候选解
        if (judge(p1[i], p2[j])) {
            ans[++cnt].a = p1[i];
            ans[cnt].b = p2[j];
        }
        if (judge(-p1[i], p2[j])) {
            ans[++cnt].a = -p1[i];
            ans[cnt].b = p2[j];
        }
    }
}

// 特判x=0的情况
if (judge(0, 1)) {
    ans[++cnt].a = 0;
    ans[cnt].b = 1;
}

3. 解的验证函数

bool judge(int x, int y) {
    int temp[105];
    memset(temp, 0, sizeof(temp));
    int a = 1, b = 1, sum = 0;
    
    // 计算多项式在x/y处的值（使用模运算避免溢出）
    for (int i = 0; i <= n; i++) {
        temp[i] = (1ll * arr[i] * a % mod + mod) % mod;
        a = 1ll * a * x % mod;
    }
    
    for (int i = n; i >= 0; i--) {
        sum = (sum + 1ll * temp[i] * b % mod + mod) % mod;
        b = 1ll * b * y % mod;
    }
    
    return sum == 0;
}

4. 结果排序与输出

// 按值从小到大排序
bool cmp(node x, node y) {
    return 1ll * x.a * y.b < 1ll * y.a * x.b;
}

sort(ans + 1, ans + 1 + cnt, cmp);

for (int i = 1; i <= cnt; i++) {
    if (ans[i].b == 1)  // 整数解
        printf("%d\n", ans[i].a);
    else  // 分数解
        printf("%d/%d\n", ans[i].a, ans[i].b);
}

关键技巧

1. 模运算验证

使用大质数模数 $1231238613$ 来验证候选解，避免直接计算可能的大数溢出。

2. 因数分解优化

只分解到 $\sqrt{n}$ 来获取所有因数，时间复杂度为 $O(\sqrt{|a_0|} + \sqrt{|a_n|})$。

3. 前导零处理

通过找到第一个非零系数来处理前导零的情况。

4. 交叉相乘排序

通过比较 $\frac{a}{b}$ 和 $\frac{c}{d}$ 时比较 $a \times d$ 和 $c \times b$ 来避免浮点数精度问题。

复杂度分析

• 因数分解：$O(\sqrt{|a_0|} + \sqrt{|a_n|})$
• 候选解验证：$O(\text{因数个数}^2 \times n)$
• 总复杂度：在数据范围内可接受

样例验证

样例：$6x^3 + 29x^2 + 14x - 24 = 0$

• $a_0 = -24$ 的因数：±1, ±2, ±3, ±4, ±6, ±8, ±12, ±24
• $a_3 = 6$ 的因数：±1, ±2, ±3, ±6
• 验证得到解：$-4$, $-\frac{3}{2}$, $\frac{2}{3}$

总结

本题的关键在于：

1. 理解有理根定理并正确应用
2. 高效生成候选解并验证
3. 处理边界情况如前导零和零解
4. 优化计算避免数值溢出

这种基于数论定理的解法在解决多项式方程有理根问题时非常经典和有效。