A. Dora 的集合 详细题解

问题重述

给定区间 $[l, r]$，初始集合包含该区间内所有整数。每次操作选择三个互不相同的数 $a, b, c$，要求它们两两互质（$\gcd = 1$），然后将它们从集合中移除。求最大操作次数。

关键观察

观察 1：奇偶性限制

在一组 $(a, b, c)$ 中，至少有两个奇数，至多一个偶数。

证明：如果同时出现两个偶数，它们的最大公约数至少为 $2$，不满足互质条件。因此，任何有效操作中，偶数个数 $\le 1$，奇数个数 $\ge 2$。

观察 2：最优策略

为了最大化操作次数，应该充分利用奇数。理想情况下，每次操作使用两个奇数和一个偶数。

观察 3：构造可行解

考虑三个连续整数：

$$2k-1,\ 2k,\ 2k+1$$

• $2k-1$ 和 $2k+1$ 是两个连续的奇数，它们互质（相邻奇数差为 $2$，但最大公约数仍为 $1$）
• $2k-1$ 和 $2k$ 是连续整数，$\gcd = 1$
• $2k$ 和 $2k+1$ 是连续整数，$\gcd = 1$

因此，这样的三元组总是可行的。

观察 4：答案公式

每次操作消耗 $2$ 个奇数和 $1$ 个偶数。由于偶数可能不够，答案受限于奇数的数量。

设区间 $[l, r]$ 中奇数的个数为 $odd$，则最大操作次数为：

$$\left\lfloor \frac{odd}{2} \right\rfloor$$

因为每次操作需要 $2$ 个奇数。

观察 5：奇数个数的计算

区间 $[l, r]$ 中奇数的个数为：

$$odd = \left\lfloor \frac{r+1}{2} \right\rfloor - \left\lfloor \frac{l}{2} \right\rfloor $$

因此答案为：

$$\text{ans} = \left\lfloor \frac{\left\lfloor \frac{r+1}{2} \right\rfloor - \left\lfloor \frac{l}{2} \right\rfloor}{2} \right\rfloor $$

时间复杂度

• 每个测试用例 $O(1)$
• 总复杂度 $O(t)$

完整代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    
    while (t--) {
        int l, r;
        cin >> l >> r;
        
        // 计算区间内奇数的个数
        int odd = (r + 1) / 2 - l / 2;
        
        // 每次操作需要 2 个奇数
        int ans = odd / 2;
        
        cout << ans << "\n";
    }
    
    return 0;
}

代码说明

1. 奇数个数计算：

   • (r + 1) / 2：$1$ 到 $r$ 中奇数的个数
   • l / 2：$1$ 到 $l-1$ 中奇数的个数
   • 相减得到 $[l, r]$ 中奇数的个数

2. 答案计算：

   • 每次操作消耗 $2$ 个奇数
   • 最大操作次数 = 奇数个数除以 $2$ 向下取整

示例验证

测试用例	奇数个数	答案
$[1,3]$	$1,3$ → $2$ 个	$2/2=1$
$[3,7]$	$3,5,7$ → $3$ 个	$3/2=1$
$[10,21]$	$11,13,15,17,19,21$ → $6$ 个	$6/2=3$
$[2,8]$	$3,5,7$ → $3$ 个	$3/2=1$
$[51,60]$	$51,53,55,57,59$ → $5$ 个	$5/2=2$
$[2,15]$	$3,5,7,9,11,13,15$ → $7$ 个	$7/2=3$
$[10,26]$	$11,13,15,17,19,21,23,25$ → $8$ 个	$8/2=4$
$[1,1000]$	$500$ 个	$500/2=250$

与样例输出完全一致。

总结

本题的核心技巧：

1. 发现操作中必须包含至少两个奇数
2. 构造连续整数三元组 $(2k-1, 2k, 2k+1)$ 证明可行性
3. 答案仅取决于区间内奇数的个数
4. $O(1)$ 时间解决，无需模拟