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;
}

上一篇:辗转相除法(求最大公约数)


下一篇:好题