题解 | #不是解的解#

题目链接

题目描述

给定 $N$ 个一元三次方程，每个方程由三元组 $(a_i, b_i, c_i)$ 描述，形式为 $x^3 + a_i x^2 + b_i x + c_i = 0$ 。你需要找到任意一个在区间 $[0, 10^6]$ 内的整数 $x$ ，使得它不是这 $N$ 个方程中任何一个的解。

数据范围： $1 \le N \le 2 \times 10^5$ , $0 \le |a_i| \le 10^6$ , $0 \le |b_i| \le 10^{12}$ , $0 \le |c_i| \le 10^{18}$ 。

解题思路

本题的数据范围相较于旧版本有了极大的提升，这使得原先的解法失效，需要我们重新分析。

1. 解的存在性分析 (鸽巢原理)

根据代数基本定理，一个一元三次方程最多有 3 个整数解。
我们总共有 $N$ 个方程，其中 $N \le 2 \times 10^5$ 。
因此，所有 $N$ 个方程的整数解的总数，最多为 $3 \times N \le 3 \times 2 \times 10^5 = 6 \times 10^5$ 个。
我们需要寻找解的范围是整数区间 $[0, 10^6]$ ，这个区间内的整数总数为 $10^6 + 1$ 个。
由于候选整数的数量（约 $10^6$ ）大于所有可能的整数解的数量（最多 $6 \times 10^5$ ），根据鸽巢原理，必然存在一个在 $[0, 10^6]$ 内的整数，它不是任何方程的解。

2. 寻找解的策略

既然解一定存在，问题就在于如何高效地找到一个。

暴力枚举（不可行）：如果我们对区间 $[0, 10^6]$ 内的每一个数 $x$ 都去检查它是否为 $N$ 个方程的解，时间复杂度将是 $\mathcal{O}(10^6 \cdot N)$ ，会严重超时。
优化策略：我们已经证明了解是存在的。一个最直接的确定性算法是，我们从 $x=0$ 开始依次向上测试，由于总根数不超过 $3N$ ，我们最多测试到 $x = 3N$ 时，必然会遇到一个非根的数。但这个最坏情况的复杂度是 $\mathcal{O}(N^2)$ ，当 $N = 2 \times 10^5$ 时依然会超时。
竞赛常用策略：在这种情况下，通常的假设是测试数据不会极端地将所有小数都设置为解。因此，一个简单且大概率能通过的策略是，从小到大依次枚举 $x = 0, 1, 2, \dots$ ，并检查它是否为任何一个方程的解。只要找到第一个不是解的 $x$ ，就立即输出。这个算法的复杂度是 $\mathcal{O}(k \cdot N)$ ，其中 $k$ 是最终找到的答案。只要 $k$ 是一个小常数（例如在几百以内），这个算法就能通过。

3. 注意事项

在计算 $x^3 + ax^2 + bx + c$ 时，由于 $x$ 和系数的范围很大，中间结果可能会超过 32 位甚至 64 位整数的范围。

对于 C++ 和 Java，需要使用 64 位整数 (long long, long)。
Python 的整数原生支持大数运算，没有溢出问题。

代码

cpp
java
python

#include <iostream>
#include <vector>

using namespace std;

struct Equation {
    long long a, b, c;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<Equation> equations(n);
    for (int i = 0; i < n; ++i) {
        cin >> equations[i].a >> equations[i].b >> equations[i].c;
    }

    // 从 0 开始向上枚举 x
    for (long long x = 0; x <= 1000000; ++x) {
        bool is_solution_for_any = false;
        for (int i = 0; i < n; ++i) {
            // 注意使用 long long 防止溢出
            if (x * x * x + equations[i].a * x * x + equations[i].b * x + equations[i].c == 0) {
                is_solution_for_any = true;
                break;
            }
        }
        if (!is_solution_for_any) {
            cout << x << endl;
            return 0;
        }
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    static class Equation {
        long a, b, c;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Equation[] equations = new Equation[n];
        for (int i = 0; i < n; i++) {
            equations[i] = new Equation();
            equations[i].a = sc.nextLong();
            equations[i].b = sc.nextLong();
            equations[i].c = sc.nextLong();
        }

        // 从 0 开始向上枚举 x
        for (long x = 0; x <= 1000000; x++) {
            boolean isSolutionForAny = false;
            for (int i = 0; i < n; i++) {
                // 注意使用 long 防止溢出
                if (x * x * x + equations[i].a * x * x + equations[i].b * x + equations[i].c == 0) {
                    isSolutionForAny = true;
                    break;
                }
            }
            if (!isSolutionForAny) {
                System.out.println(x);
                return;
            }
        }
    }
}

import sys

def solve():
    n_str = sys.stdin.readline()
    if not n_str: return
    n = int(n_str)
    
    equations = []
    for _ in range(n):
        a, b, c = map(int, sys.stdin.readline().split())
        equations.append({'a': a, 'b': b, 'c': c})

    # 从 0 开始向上枚举 x
    for x in range(1000001):
        is_solution_for_any = False
        for eq in equations:
            if x**3 + eq['a'] * x**2 + eq['b'] * x + eq['c'] == 0:
                is_solution_for_any = True
                break
        
        if not is_solution_for_any:
            print(x)
            return

solve()

算法及复杂度

算法: 枚举、鸽巢原理
时间复杂度: 设找到的最小非负整数解为 $k$ 。算法的复杂度为 $\mathcal{O}(k \cdot N)$ 。在最坏的情况下， $k$ 可能接近 $3N$ ，复杂度为 $\mathcal{O}(N^2)$ ，但通常在竞赛中 $k$ 会是一个小常数，使得该解法能够通过。
空间复杂度: 我们需要存储 $N$ 个方程的系数。因此，空间复杂度为 $\mathcal{O}(N)$ 。