描述
一家商店的巧克力分为两类包装:
1.散装:一个一个的;
2.盒装:a个巧克力为一盒.
一位顾客购买巧克力时有个奇怪的规矩(假设他需要买x个):
如果x%a>=a/2他就决定全买成盒装,不会再一个一个买了,这会使他买的巧克力比他原来想要的多,此时商家就会高兴。
现在给出这位顾客想要买的巧克力数量的区间 [l,r] (也就是说顾客会选择从l到r的任意数),请你判断是否存在一个整数a使商家在任何情况下都高兴。
输入
第一行输入t 个(t<1000)--案例个数
接下来tt行每行输入两个数:x的范围l和r (0<l<=r<5000),两数中间以一个空格隔开
输出
输出为t行。对于每个案例,如果存在整数a使得商家在顾客的所有选择下都会高兴,则输出"YES",否则输出"NO"(输出不包含"")。
输入样例 1
3
3 4
1 2
120 150
输出样例 1
YES NO YES
思路:
其实是一个数学问题。可以推算一下。首先a一定是从2开始算起(a==1的话无意义)。
如果a<l,(单独考虑2,3的情况发现没有合适的a)考虑到l与r之间肯定有合数,那么在遍历的过程中,只要a==2(或其他合适的因数),x%a将在某一个x值处取到0,不符合题意,舍去;
如果a>l&&a>r,那么x%a==l或==r,这就是一个确定的数了,接下来只要考虑让这两个数值>=a/2,即联立四个方程组求解取交集
a>l
a>r
l>=a/2
r>=a/2
解得r<a<=2l
所以当右边界小于等于左边界的时候都是不存在的,输出NO就可以了。
(为什么不考虑中间:我先考虑的边界,然后发现考虑到最大的边界的时候就过了)
代码如下:
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int l, r;
cin >> l >> r;
if (2 * l <= r)
cout << "NO" << endl;
else
cout << "YES" << endl;
}
return 0;
}