提示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)。