翻译:
描述:考虑由[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;
}