[数据结构与算法]D13：GCD Arrays（最大公约数数列，附题解）

原题：Problem - B - Codeforces

翻译：

描述：考虑由[l，r]范围内的所有整数组成的数组a。比如：如果l=3，r=7，那a=[3，4，5，6，7]。

? ? ? ? ? 给定l、r和k，求问在最多k次执行如下操作后，数组a中各元素的最大公约数gcd(a)是否可能大于1。

操作如下：

• 从a中任选2个数字；
• 从数组中删除其中一个；
• 把两数的的乘积放回数组a；

gcd(b)表示数组b中各个整数的最大公约数(gcd)；

输入：第一行：一个范围为[1，10^5]的整数t?，表示测试用例的数量；

? ? ? ? ? ? 每个测试用例的输入包含3个非负整数l、r和k (1≤l≤r≤10^9,0≤k≤r-l)；

输出：对于每个测试用例，如果通过最多执行k操作可以使对应数组的最大公约数大于1，则输出“YES”，否则输出“NO”(不区分大小写)。

代码：这题用了分类讨论思想，①l=r的情况，此时我们只需要判断l是否大于1，大于就输出“是”；

②l<r的情况，根据题意我们可以知道，如果数列a中只有偶数，那么最大公约数至少是2，如果有奇有偶，那最大公约数大概率是1，所以只需要确定数列a是否满足以下条件：（满足就输出“是”）

一是数列a中是否有偶数；

二是数列a中的奇数个数是否小于最大操作数k；

PS：显然，我们每次的操作应该是：取出a中的一个奇数和一个偶数，删掉奇数，放回乘积（奇*偶=偶)，因为这样可使a中全为偶数w

#include<iostream>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--){
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		int f=0;
		if(l==r&&l>1) f=1;
		else{
			int sy=r-l+1;
			int jishu=sy/2;
			if(l%2&&r%2) jishu++;
			if(sy>jishu&&jishu<=k) f=1;
		}
		if(f) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}