[数据结构与算法]GCD Arrays（gcd/数论/思维）

题目

题意：给定一个取值区间为$[l,r]$的数组，有$k(0<=k<=r?l)$次操作，每次操作可以选择数组中的两个元素，合并为积的形式，放回数组。问经过最多k次操作后，数组元素的gcd能否大于1。

思路：要使多个数的gcd大于1，首先最容易得到的就是2了。因此，最优策略，就是贪心地消灭掉所有的奇数。注意考虑下区间只有一个数的情况。

#include<bits/stdc++.h> 
using namespace std;
const int maxn = 110;

int l, r, k;
void solve() {
	scanf("%d%d%d", &l, &r, &k);
	// 只有一个数，特判下 
	if (l == r) {
		printf("%s\n", l > 1 ? "YES" : "NO");
	} else {
		int len = r - l + 1;
		// num 用于 求区间奇数个数 
		int num = len / 2;
		if (len & 1) num += (l & 1);
		printf("%s\n", k >= num ? "YES" : "NO");
	}
}
int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		solve();
	}
}

/*
1 2 3 4 5

1 2 3 4 5 6 7

4 5 6 7 8 9 10
*/