正经题解｜公约数序列

提示1

如果一个数组的最大公约数大于 $1$，那么说明数组中的每个元素都有一个共同的质因数。

提示2

若 $a$ 为奇数，$b$ 为偶数，那么 $\gcd(a, b)$ 的值为多少？

题目解析

要使整个数组的最大公约数大于 $1$，每个元素都必须有一个共同的质因数，因此我们需要找到数组中出现次数最多的质因数，然后将有这个质因数的数字与没有这个质因数的元素合并，答案就是 数组的大小 - 出现次数最多质因数的出现次数。
因为数字是连续的，所以出现次数最多的质因数一定是 $2$。因此，我们需要做的最少操作次数就是给定范围 $[l, r]$ 内奇数的数量。

令 $odd(x)$ 表示小于等于 $x$ 的奇数的数量，那么答案就是 $odd(r) - odd(l-1)$。

当需要做的最少操作次数小于等于 $k$ 时答案为 YES 否则为 NO。
需要注意一个特殊情况是当 $l=r$ 时， 如果 $l = r = 1$ 那么显然答案为 NO，否则若 $l = r > 1$ 答案显然为 YES。

AC代码

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

int odd(int x) {
    return x + 1 >> 1;
}

bool check(int l, int r, int k) {
    if (l == r) return l > 1;
    return odd(r) - odd(l - 1) <= k;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int l, r, k;
        cin >> l >> r >> k;
        cout << (check(l, r, k) ? "YES" : "NO") << '\n';
    }
    return 0;
}

复杂度分析

对于每个查询我们可以直接计算出 odd(l - 1) 和 odd(r)，所以对于每个用例时间复杂度为 $O(1)$。