Codeforces1629B.GCDArrays——基础算法解析与思路分享

This way

题意&＃xff1a;

给你一个区间[l,r]的所有数和你的最大操作次数k&＃xff0c;你每次可以做这样一个操作&＃xff1a;将你手上的数中拿出两个相乘之后放回去。
问你最终是否能将手上的所有数的gcd变成不是1.

题解&＃xff1a;

既然gcd不是1&＃xff0c;那就要将所有数变成某个数的倍数。那肯定猜测是2的倍数啊&＃xff0c;每两个变成一个显然是最优的&＃xff0c;可以自己造例子验证以下。当然有一点&＃xff1a;只有一个数的时候就不需要了。
那么怎么变呢&＃xff0c;每次拿一个奇数和一个偶数相乘即可。
拿就相当于只需要看奇数的数量是否<&＃61;k。

#include
using namespace std;
int main()
{int t;scanf("%d",&t);while(t--){int l,r,k;scanf("%d%d%d",&l,&r,&k);if(l&＃61;&＃61;r){printf("%s\n",l&＃61;&＃61;1?"NO":"YES");continue;}int num&＃61;(r-l&＃43;1)/2&＃43;(l%2&&r%2);printf("%s\n",num<&＃61;k?"YES":"NO");}return 0;
}