提示1 如果一个数组的最大公约数大于 111，那么说明数组中的每个元素都有一个共同的质因数。 提示2 若 aaa 为奇数，bbb 为偶数，那么 gcd⁡(a,b)\gcd(a, b)gcd(a,b) 的值为多少？ 题目解析 要使整个数组的最大公约数大于 111，每个元素都必须有一个共同的质因数，因此我们需要找到数组中出现次数最多的质因数，然后将有这个质因数的数字与没有这个质因数的元素合并，答案就是 数组的大小 - 出现次数最多质因数的出现次数。 因为数字是连续的，所以出现次数最多的质因数一定是 222。因此，我们需要做的最少操作次数就是给定范围 [l,r][l, r][l,r] 内奇数的数量。 令 odd(x)odd(x)odd(x) 表示小于等于 xxx 的奇数的数量，那么答案就是 odd(r)−odd(l−1)odd(r) - odd(l-1)odd(r)−odd(l−1)。 当需要做的最少操作次数小于等于 kkk 时答案为 YES 否则为 NO。 需要注意一个特殊情况是当 l=rl=rl=r 时， 如果 l=r=1l = r = 1l=r=1 那么显然答案为 NO，否则若 l=r>1l = r > 1l=r>1 答案显然为 YES。 AC代码 复杂度分析 对于每个查询我们可以直接计算出 odd(l - 1) 和 odd(r)，所以对于每个用例时间复杂度为 O(1)O(1)O(1)。