自动搬运

查看原文

来自洛谷，原作者为

	Chenyichen0420 BS leads to GS || To be or to bee || To be or to be not

搬运于2025-08-24 21:15:07，当前版本为作者最后更新于2023-08-17 13:16:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简要题意

给出 $n$ 个关于 $x$ 的一元三次方程，求出任意一个整数 $x$ 使其均不是这些方程的解。

主思路

作为一道正常的题，我们暴力枚举肯定不行，其复杂度显然过大。

这时我们能轻松地想到一种有点瞎搞的做法：随机化。

我们来分析一下其时间复杂度：

首先有一个数学上的常识：对于一个一元 $k$ 次方程，其实数解最多有 $k$ 个。那么对于此题的 $3$ 次方程，每个方程最多有 $3$ 个实数解。总共最多也只有 $6\times10^5$ 个解。那么对于一个长度为 $1000001$ 的区间，一个整数满足其均不是这些方程的解的概率实际上在 $0.4$ 以上。平均算下来枚举 $3$ 次左右就可以成功了。

但是本地调试和提交测评的时候要注意一些坑点：

rand() 在 Windows 系统中的值域为 $0$ 至 $32767$，需要将两个 rand() 乘起来。

我们还需要强转一下 long long 再取模，因为 rand() 在 Linux 系统中的值域更大，乘起来会炸 int，所以如果想兼容 Windows 和 Linux 的话需要进行上述操作。

考虑到概率过小的超时，可以用 srand() 刷新一下运气，这样每次运行都极大概率能输出不相同的值。

其具体用法为在主函数中加上 srand((unsigned)time(0))。不过请添加上 ctime 头文件。

这样，当我们输入并存储完毕后，就可以随机枚举答案并验证，如果通过就直接输出，否则继续随机枚举。

下面附上代码。

#include<iostream>
#include<algorithm>
#include<ctime>
using namespace std;
#define int long long
int a[200005], b[200005], c[200005], n;
inline bool check(int ps) {
	for (int i = 1; i <= n; ++i)
		if (ps * ps * ps + a[i] * ps * ps + b[i] * ps + c[i] == 0) return 0;
	return 1;
}
signed main() {
	ios::sync_with_stdio(0);
	srand((unsigned)time(0));
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> a[i] >> b[i] >> c[i];
	for (register int i = 1; i <= n; ++i) {
		int pos = rand() * 1ll * rand() % 1000000;
		if (check(pos)) {
			cout << pos << endl;
			return 0;
		}
	}
}