翻译：CF2007A Dora's Set

Jerrycyx · 2024-10-11 14:25:54 · 个人记录

题目描述

Dora 有一个包含整数的集合 s 。一开始，她将 [l,r] 中的所有整数放入集合 s 中。即整数 x 最初包含在集合中当且仅当 l \le x \le r 。然后执行以下操作:

• 从集合 s 中选择三个不同的整数 a,b,c ，使得 \gcd(a,b) = \gcd(b,c) = \gcd(a,c) = 1 。
• 然后，从集合 s 中删除这三个整数。

你能执行的最大操作数是多少?

输入格式

输入包含多组测试数据。第一行一个整数 t (1 \le t \le 500) 表示测试数据数量。

对于每组测试数据：输入仅一行，两个整数 l,r (1 \le l \le r \le 1000)，表示 s 中整数的范围。

输出格式

对于每组测试数据：输出一个整数，表示可以执行的最大操作数。

说明/提示

在第一个样例中，你可以在唯一的操作中选择 a=1,b=2,c=3，因为 \gcd(1, 2) = \gcd(2, 3) = \gcd(1, 3) = 1，此时集合中没有更多的整数，因此不能执行更多的操作。

在第二个样例中，你可以在唯一的操作中选择 a=3,b=5,c=7。

在第三个样例中，第一个操作可以选择 a=11、b=19、c=20，第二个操作可以选择 a=13、b=14、c=15，第三个操作可以选择 a=10 、b=17、c=21。经过这三种操作后，集合 s 包含如下整数: 12，16，18。可以证明，不可能执行多于 3 次操作。