Burnside 先手从区间 中选一个整数 ，Edisnrub 后手从区间 中选一个整数 。 若 是合数则 Burnside 胜，否则 Edisnrub 胜。双方都采取最优策略，问谁必胜。
关键转化
· 后手 Edisnrub 在知道 的情况下选择 ，她的目标是让 为质数（如果可能的话）。 · 先手 Burnside 的目标是选择一个 ，使得 无论 Edisnrub 选哪个 ， 都是合数。
换句话说，Burnside 胜当且仅当存在某个 ，使得对于 所有 ， 都是合数。 等价地：对于某个 ，区间 内的所有整数都是合数。
若不存在这样的 ，则 Edisnrub 总能针对 Burnside 选的 找到一个 使得和为质数，因此 Edisnrub 胜。
问题重述
记：
· 为后手可选数字的个数。 · 固定 后， 是一个长度为 的连续整数区间：。
我们要判断是否存在 ，使得区间 中 全部是合数。
若存在，输出 "Burnside"；否则输出 "Edisnrub"。
数据范围与预处理
，因此 的最大值为 。
我们可以用 欧拉筛 或 埃氏筛 预处理 内的质数表，然后标记每个数是否为合数。
为了快速判断一个区间是否全为合数，我们对合数数组做 前缀和：
· comp[i] = 1 若 是合数，否则 0。 · pref[i] = sum_{k=2}^{i} comp[k]。
那么区间 内合数的个数为 pref[b] - pref[a-1]。若该值等于区间长度 ，则全为合数。
算法步骤
- 读入 。
- 计算 。
- 确定需要判定的区间起点范围： 对于 ，对应区间为 ，其起点范围为 。
- 筛出 内的质数，得到合数标记数组，并计算前缀和。
- 遍历起点 start 从 l1+l2 到 r1+l2： · 区间终点 end = start + L - 1。 · 检查该区间是否全部为合数：pref[end] - pref[start-1] == L。 · 若找到这样的区间，输出 "Burnside" 并结束。
- 若循环结束未找到，输出 "Edisnrub"。
复杂度分析
· 质数筛：，，非常快。 · 前缀和：。 · 判定循环：最坏 次，每次 。 · 总复杂度：，完全可行。
正确性说明
· 若存在一个全合数区间，则 Burnside 选对应的 ，Edisnrub 无论如何选 都会得到合数，Burnside 胜。 · 若不存在这样的区间，则对于 Burnside 选的任意 ，区间 中至少有一个质数。Edisnrub 可以选择对应的 使得和为质数，从而获胜。 · 由于双方都采取最优策略，上述推理是完备的。
代码实现（C++）
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 200000;
int main() {
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
int L = r2 - l2 + 1;
int max_sum = r1 + r2;
// 筛法求质数
vector<bool> is_prime(max_sum + 1, true);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i * i <= max_sum; ++i) {
if (is_prime[i]) {
for (int j = i * i; j <= max_sum; j += i)
is_prime[j] = false;
}
}
// 合数标记 + 前缀和
vector<int> comp(max_sum + 1, 0);
for (int i = 2; i <= max_sum; ++i)
if (!is_prime[i]) comp[i] = 1;
vector<int> pref(max_sum + 1, 0);
for (int i = 2; i <= max_sum; ++i)
pref[i] = pref[i-1] + comp[i];
// 枚举区间起点
for (int start = l1 + l2; start <= r1 + l2; ++start) {
int end = start + L - 1;
if (end > max_sum) continue; // 防止越界（实际上 end <= r1+r2 恒成立）
if (pref[end] - pref[start-1] == L) {
cout << "Burnside" << endl;
return 0;
}
}
cout << "Edisnrub" << endl;
return 0;
}
样例验证
输入：1 2 3 4
· · 枚举 ： · ：区间 ，含质数 5 → 否 · ：区间 ，含质数 5 → 否 · 无全合数区间 → 输出 "Edisnrub"，符合样例。
小结
本题本质是 区间全合数判定，通过质数筛 + 前缀和可以高效解决。注意边界处理，以及筛法范围取到 即可。
暂无评论