← 返回题目列表

Codeforces · 1629/B

B. GCD 阵列

中文机器翻译题面 查看原题

考虑由 $$$[l, r]$$$ 范围内的所有整数组成的数组 $$$a$$$。例如,如果 $$$l = 3$$$ 且 $$$r = 7$$$,则 $$$a = [3, 4, 5, 6, 7]$$$。

给定$$$l$$$、$$$r$$$和$$$k$$$,在执行最多$$$k$$$次操作后,$$$\gcd(a)$$$是否可能大于$$$1$$$?

- 从 $$$a$$$ 中选择 $$$2$$$ 数字。
- 从数组中永久删除其中每一个的出现。
- 将他们的产品重新插入$$$a$$$。

$$$\gcd(b)$$$ 表示 $$$b$$$ 中整数的最大公约数 (GCD)。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的输入由一行组成,其中包含 $$$3$$$ 非负整数 $$$l$$$、$$$r$$$ 和 $$$k$$$ ($$$1 \leq l \leq r \leq 10^9, \enspace 0 \leq k \leq r - l$$$)。

输出

对于每个测试用例,如果通过最多执行 $$$k$$$ 操作可以使相应数组的 GCD 大于 $$$1$$$,则打印“YES”,否则打印“NO”(不区分大小写)。

示例

输入 #1

9
1 1 0
3 5 1
13 13 0
4 4 0
3 7 4
4 10 3
2 4 0
1 7 3
1 5 3

输出 #1

NO
NO
YES
YES
YES
YES
NO
NO
YES

注意

对于第一个测试用例,$$$a = [1]$$$,因此答案为“NO”,因为数组中唯一的元素是 $$$1$$$。

对于第二个测试用例,数组是 $$$a = [3, 4, 5]$$$ 并且我们有 $$$1$$$ 操作。第一次操作后,数组可以更改为: $$$[3, 20]$$$、$$$[4, 15]$$$ 或 $$$[5, 12]$$$ 所有这些的最大公约数都等于 $$$1$$$,因此答案为“否”。

对于第三个测试用例,$$$a = [13]$$$,因此答案为“YES”,因为数组中唯一的元素是 $$$13$$$。

对于第四个测试用例,$$$a = [4]$$$,因此答案为“YES”,因为数组中唯一的元素是 $$$4$$$。